ECCC-Report TR22-059https://eccc.weizmann.ac.il/report/2022/059Comments and Revisions published for TR22-059en-usWed, 27 Apr 2022 06:46:54 +0300
Paper TR22-059
| Diameter versus Certificate Complexity of Boolean Functions |
Siddhesh Chaubal,
Anna Gal
https://eccc.weizmann.ac.il/report/2022/059In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we show that diameter is always upper bounded by certificate complexity. We argue that estimating diameter may help to get improved bounds on certificate complexity in terms of sensitivity, and other measures.
Previous results due to Lin and Zhang imply that $s(f) \ge \Omega(n^{1/3})$ for transitive functions with constant alternating number. We improve and extend this bound and prove that $s(f) \ge \sqrt{n}$ for transitive functions with constant alternating number, as well as for transitive functions with constant diameter. We also show that $bs(f) \ge \Omega(n^{3/7})$ for transitive functions under the weaker condition that the ``minimum'' diameter is constant.
Furthermore, we prove that the log-rank conjecture holds for functions of the form $f(x \oplus y)$ for functions $f$ with diameter bounded above by a polynomial of the logarithm of the Fourier sparsity of the function $f$.Wed, 27 Apr 2022 06:46:54 +0300https://eccc.weizmann.ac.il/report/2022/059