Composition Limits and Separating Examples for Some Boolean Function Complexity Measures

Block sensitivity (bs(f)), certificate complexity (C(f)) and fractional certificate complexity (C*(f)) are three fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) ≤ C*f ≤ C(f) =O(bs(f) 2 ). We provide an infinite family of examples for which ... View More