Randomized certificate complexity was introduced by Aaronson as a randomized version of certificate complexity [1]}, and subsequently shown to be equivalent (up to constant factors) to fractional block sensitivity and fractional certificate complexity [2]}, [3]}, [4]}.
