Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-027 | 31st July 2014 14:06

A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity

RSS-Feed




Revision #1
Authors: Andris Ambainis, Krisjanis Prusis
Accepted on: 31st July 2014 14:06
Downloads: 1377
Keywords: 


Abstract:

Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity and 0-sensitivity and 0-block sensitivity.
Previously the best known lower bound was $C_1(f)\geq \frac{bs_0(f)}{2 s_0(f)}$, achieved by Kenyon and Kutin. We improve this to $C_1(f)\geq \frac{3 bs_0(f)}{2 s_0(f)}$. While this improvement is only by a constant factor, this is quite important, as it precludes achieving a superquadratic separation between $bs(f)$ and $s(f)$ by iterating functions which reach this bound. In addition, this bound is tight, as it matches the construction of Ambainis and Sun up to an additive constant.


Paper:

TR14-027 | 21st February 2014 10:39

A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity





TR14-027
Authors: Andris Ambainis, Krisjanis Prusis
Publication: 28th February 2014 15:02
Downloads: 2637
Keywords: 


Abstract:

Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity and 0-sensitivity and 0-block sensitivity.
Previously the best known lower bound was $C_1(f)\geq \frac{bs_0(f)}{2 s_0(f)}$, achieved by Kenyon and Kutin. We improve this to $C_1(f)\geq \frac{3 bs_0(f)}{2 s_0(f)}$. While this improvement is only by a constant factor, this is quite important, as it precludes achieving a superquadratic separation between $bs(f)$ and $s(f)$ by iterating functions which reach this bound. In addition, this bound is tight, as it matches the construction of Ambainis and Sun up to an additive constant.



ISSN 1433-8092 | Imprint