We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions G with C(G)=Ω~(deg~(G)4), where C denotes certificate complexity and deg~ denotes 1/3-approximate degree. This is optimal up to polylogarithmic factors, since every total Boolean function f satisfies C(f)≤O(deg~(f)4) by the classical block-sensitivity bounds of Nisan and Nisan--Szegedy. Thus the result closes the gap between these two measures and improves the previously best known separation C(f)=Ω~(deg~(f)3) by Balodis, Ben-David, Göös, Jain, and Kothari. The construction starts from the partial function they used to quadratically separate 0-certificate complexity from unambiguous 1-certificate complexity. It already has the required certificate hardness, but its 0-certificates are unstructured, which blocks the derivation of a low-degree verifier. We keep its 1-condition and restrict the 0-inputs to those certified by a structured family whose validity admits a low-degree approximant, while preserving the quadratic hardness. The partial function with its low-degree verifier is then fed through the cheat-sheet framework to yield the total function G with the claimed separation. The main technical ingredient is an approximate polynomial that verifies the certificate in degree O~(n). The verifier forms a low-degree count W of the candidate 1-certificates that remain compatible with the asserted 0-certificate, and tests whether this count is zero. Crucially, the construction ensures that W never exceeds O~(n), instead of the Θ(n2) candidate pairs it counts bringing the verification down to degree O~(n).
We investigate the relation between the block sensitivity bs(f) and fractional block sensitivity fbs(f) complexity measures of Boolean functions. While it is known that fbs(f)=O(bs(f)2), the best known separation achieves fbs(f)=(321+o(1))bs(f)3/2. We improve the constant factor and show a family of functions that give fbs(f)=(61−o(1))bs(f)3/2.
We study a natural complexity measure of Boolean functions known as the rational degree. Denoted rdeg(f), it is the minimal degree of a rational function that is equal to f on the Boolean hypercube. For total functions f, it is conjectured that rdeg(f) is polynomially related to the Fourier degree of f, deg(f). Towards this conjecture, we show that: - Symmetric functions have rational degree at least Ω(deg(f)) and unate functions have rational degree at least deg(f). We observe that both of these lower bounds are asymptotically tight. - Read-once AC and TC formulae have rational degree at least Ω(deg(f)). If these formulae contain parity gates, we show a lower bound of Ω(deg(f)1/2d), where d is the depth. - Almost every Boolean function on n variables has rational degree at least n/2−O(n). In contrast, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model. In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity.