8
$\begingroup$

The recent establishment of the relation $bs(f)=O(s(f)^4)$ goes through Gotsman,Linial .

Can the same approach get to $O(s(f)^2)$ or is there an essential limitation to the approach?

$\endgroup$
  • 1
    $\begingroup$ This is discussed in the concluding remarks of Hao Huang's paper (under the third bullet). Huang writes: "Perhaps one could close this gap by directly applying the spectral method to boolean functions instead of to the hypercubes." $\endgroup$ – Gamow Jul 31 at 15:28
16
$\begingroup$

From the paper: what is actually proven is, in Theorem 1.4, $$ \forall f\colon\{0,1\}^n \to \{0,1\}, \qquad s(f) \geq \sqrt{\deg f} \tag{1} $$ which cannot be improved (it is tight for some functions). Then it is combined with the previously known result of Nisan and Szegedy [1], $$ \forall f\colon\{0,1\}^n \to \{0,1\}, \qquad \deg f \geq \sqrt{\frac{1}{2}\operatorname{bs} f} \tag{2} $$ (a separation, incidentally, you asked about a few years back). From this survey [2] (see Table 1), referencing [3], (2) cannot be improved beyond $$ \operatorname{bs} f \gtrsim (\deg f)^{\log_3 6} $$ where $\log_3 6 \approx 1.63$. So this avenue of using the degree as a proxy cannot give a quadratic sensitivity upper bound on the the block sensitivity.

On the other hand, it's possible that using similar techniques (i.e., interlacing eigenvalues of signed matrices) but on different objects (first and foremost, without using the degree as a proxy) may lead to sharper bounds. This is explicitly stated as open question in Huang's paper [4]:

Perhaps one could close this [quadratic vs. quartic] gap by directly applying the spectral method to boolean functions instead of to the hypercubes.


[1] Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Comput. Complexity, 4:462–467, 1992. doi:10.1007/BF01263419

[2] Pooya Hatami, Raghav Kulkarni, and Denis Pankratov, Variations on the Sensitivity Conjecture. Theory of Computing Graduate Survey, 2011. https://theoryofcomputing.org/articles/gs004/

[3] Noam Nisan and Avi Wigderson. On rank vs. communication complexity. Combinatorica, 15:557–565, 1995. doi:10.1007/BF01192527

[4] Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. arXiv:1907.00847, 2019. https://arxiv.org/abs/1907.00847

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.