Randomized query complexity can beat certificate complexityResearch Paper
Query complexity measures how many input bits an algorithm must read to evaluate a Boolean function . For total functions (defined on every input) the classical, randomized and quantum measures are polynomially related, and a large part of the field consists of pinning down the best exponents in these relations; see the survey of…