Composition limits and separating examples for some Boolean function complexity measures

Justin Gilmer, Michael Saks, Srikanth Srinivasan

Block sensitivity ($bs(f)$), certificate complexity ($C(f)$) and fractional certificate complexity ($C^{\ast }(f)$) are three fundamental combinatorial measures of complexity of a boolea…