ECCC-Report TR14-027https://eccc.weizmann.ac.il/report/2014/027Comments and Revisions published for TR14-027en-usThu, 31 Jul 2014 14:06:51 +0300
Revision 1
| A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity |
Krisjanis Prusis,
Andris Ambainis
https://eccc.weizmann.ac.il/report/2014/027#revision1Sensitivity, 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.Thu, 31 Jul 2014 14:06:51 +0300https://eccc.weizmann.ac.il/report/2014/027#revision1
Paper TR14-027
| A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity |
Krisjanis Prusis,
Andris Ambainis
https://eccc.weizmann.ac.il/report/2014/027Sensitivity, 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.Fri, 28 Feb 2014 15:02:52 +0200https://eccc.weizmann.ac.il/report/2014/027