<p>From the paper: what is actually proven is, in Theorem 1.4,
<span class="math-container">$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad s(f) \geq \sqrt{\deg f} \tag{1}
$$</span>
which cannot be improved (it is tight for some functions). Then it is combined with the previously known result of Nisan and Szegedy [1], 
<span class="math-container">$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad \deg f \geq \sqrt{\frac{1}{2}\operatorname{bs} f}
\tag{2}
$$</span>
(a separation, incidentally, <a href="https://cs.stackexchange.com/questions/37129/block-sensitivity-and-degree">you asked about a few years back</a>). From <a href="https://theoryofcomputing.org/articles/gs004/" rel="nofollow noreferrer">this survey</a> [2] (see Table 1), referencing [3], (2) cannot be improved beyond 
<span class="math-container">$$
\operatorname{bs} f \gtrsim (\deg f)^{\log_3 6}
$$</span>
where <span class="math-container">$\log_3 6 \approx 1.63$</span>. So this avenue of using the degree as a proxy <em>cannot</em> give a quadratic sensitivity upper bound on the the block sensitivity.</p>

<p>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]:</p>

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

<hr>

<p>[1] Noam Nisan and Mario Szegedy. <em>On the degree of Boolean functions as real polynomials</em>. Comput. Complexity, 4:462–467, 1992. <a href="https://link.springer.com/article/10.1007%2FBF01263419" rel="nofollow noreferrer">doi:10.1007/BF01263419</a></p>

<p>[2] Pooya Hatami, Raghav Kulkarni, and Denis Pankratov, <em>Variations on the Sensitivity Conjecture.</em> Theory of Computing Graduate Survey, 2011. <a href="https://theoryofcomputing.org/articles/gs004/" rel="nofollow noreferrer">https://theoryofcomputing.org/articles/gs004/</a></p>

<p>[3] Noam Nisan and Avi Wigderson. <em>On rank vs. communication complexity</em>. Combinatorica, 15:557–565, 1995. <a href="https://link.springer.com/article/10.1007%2FBF01192527" rel="nofollow noreferrer">doi:10.1007/BF01192527</a></p>

<p>[4] Hao Huang. <em>Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture.</em> arXiv:1907.00847, 2019.  <a href="https://arxiv.org/abs/1907.00847" rel="nofollow noreferrer">https://arxiv.org/abs/1907.00847</a></p>

CC BY-SA 4.0
2019-07-31T15:39:08.870Z
2019-08-27T22:14:09.817Z
2019-08-27T22:14:09.817Z
Clement C.
<p><a href="https://arxiv.org/pdf/1907.00847.pdf" rel="noreferrer">The recent establishment of the relation <span class="math-container">$bs(f)=O(s(f)^4)$</span></a> goes through <a href="https://www.sciencedirect.com/science/article/pii/0097316592900608" rel="noreferrer">Gotsman,Linial</a> .</p>

<blockquote>
  <p>Can the same approach get to <span class="math-container">$O(s(f)^2)$</span> or is there an essential limitation to the approach?</p>
</blockquote>

CC BY-SA 4.0
2019-07-31T15:28:09.923Z
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."*
Gamow
<cc.complexity-theory><boolean-functions>
On the sensitivity conjecture?
Turbo
# On the sensitivity conjecture?

(Asked by: username_0 on 2019-07-31)

[The recent establishment of the relation $bs(f)=O(s(f)^4)$](https://arxiv.org/pdf/1907.00847.pdf) goes through [Gotsman,Linial](https://www.sciencedirect.com/science/article/pii/0097316592900608) .

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

**Tags:** cc.complexity-theory, boolean-functions
> **Comments:**
> **username_1**: 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."*  

---

## 1 answers

### Answer by username_2 on 2019-07-31. Score: 17 | Accepted answer

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](https://cs.stackexchange.com/questions/37129/block-sensitivity-and-degree)). From [this survey](https://theoryofcomputing.org/articles/gs004/) [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](https://link.springer.com/article/10.1007%2FBF01263419)

[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](https://link.springer.com/article/10.1007%2FBF01192527)

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


---

