<p>Here is what <a href="http://www.scottaaronson.com/blog/?p=453">Scott Aaronson</a> has to say on the subject:</p>

<blockquote>
  <p>What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity measures: the decision-tree complexity of $f$, the certificate complexity of $f$, the randomized query complexity of $f$, the quantum query complexity of $f$, the degree of $f$ as a real polynomial, you name it.  So if, as is conjectured, sensitivity and block-sensitivity are polynomially related, then sensitivity—arguably the most basic of all Boolean function complexity measures—ceases to be an outlier and joins a large and happy flock.</p>
</blockquote>

<p>Checking other relevant literature doesn't offer any other compelling implications:</p>

<ul>
<li><a href="http://link.springer.com/article/10.1007%2FBF01263419">Nisan and Szegedy</a> describe the question but offer no motivation at all.</li>
<li><a href="http://traell.cs.uchicago.edu/files/tr_authentic/TR-2001-22.ps">Kenyon and Kutin</a> mention that is is a "natural open question".</li>
<li><a href="http://www.sciencedirect.com/science/article/pii/0097316592900608">Gotsman and Linial</a> give a somewhat contrived equivalent problem (Conjecture 5.33 on page 18 of the following paper).</li>
<li><a href="http://theoryofcomputing.org/articles/gs004/gs004.pdf">P. Hatami, Kulkarni and Pankratov</a>, in their comprehensive survey on the problem, also offer no motivation, but they have several equivalent formulations. For example, the sensitivity conjecture is equivalent to the conjecture that the parity decision complexity of a function is polynomially bounded by the sensitivity. Conjecture 5.31 on page 17, due to Shi, is one reformulation that doesn't mention sensitivity at all.</li>
<li><a href="http://eccc.hpi-web.de/report/2014/152/">Ambainis, Bavarian, Gao, Mao, Sun and Zao</a> state that the conjecture "originates from the theory of complexity measures of Boolean functions and
decision tree complexity", and generally offer the same type of motivation as Scott Aaronson does. Their recent preprint is the last word on the conjecture (as of December 2014).</li>
</ul>

CC BY-SA 3.0
2014-12-05T21:18:32.363Z
2014-12-05T21:18:32.363Z
Yuval Filmus
<p>As I understand it, the original motivation was to study CREW PRAM (consecutive read exclusive write parallel RAM) model. In this model, several processors compute a function with shared memory access, but with no write conflicts. <a href="http://dl.acm.org/citation.cfm?doid=800070.802196" rel="nofollow">Stephen Cook and Cynthia Dwork</a> and Rudiger Reischuk ("A lower time-bound for parallel random access machines without simultaneous
writes.") showed that $\Omega( \log(s(f)) )$ is a lower bound on the number of steps required to compute $f$ on CREW PRAM. Let $CREW(f)$ denote the minimum number of steps required to compute $f$ in CREW PRRAM. Thus, Cook, Dwork, and Reischuk showed that</p>

<p>$CREW(f) = \Omega(\log s(f))$</p>

<p>Later, <a href="http://dl.acm.org/citation.cfm?doid=73007.73038" rel="nofollow">Noam Nisan</a> tweaked the definition of sensitivity to <em>characterize</em> $CREW(f)$ up to constant multiplicative factors. The tweaked definition is, of course, block sensitivity. I.e.,</p>

<p>$CREW(f) = \Theta(\log bs(f))$</p>

<p>The natural question then arises whether $CREW(f) = O(\log s(f))$? This is essentially the sensitivity conjecture. </p>

<p>Whether nowadays the implication of sensitivity giving a tight characterization of $CREW(f)$ is compelling or not - I cannot judge. As pointed out in another response, it turned out that block sensitivity is included in a large class of polynomially related complexity measures, while sensitivity is not known to belong to that class.</p>

CC BY-SA 3.0
2014-12-15T18:45:29.437Z
2014-12-21T07:54:55.543Z
2014-12-21T07:54:55.543Z
Denis Pankratov
<p>Let $f$ be a boolean function with sensitivity $s(f)$ and block sensitivity $bs(f)$.</p>

<p>The Sensitivity-Block sensitivity conjecture conjecture states that there is a $c&gt;0$ such that $\forall f,\mbox{ }bs(f)\leq s(f)^c$.</p>

<p>What are the implications of the truth and falsehood of this conjecture?</p>

<p>Please quote references as well.</p>

CC BY-SA 3.0
2014-12-08T08:56:00.887Z
Please consider making the question and its answer more useful by providing definitions of the terms sensitivity and block sensitivity.
Jan Johannsen
CC BY-SA 4.0
2019-07-06T08:28:50.430Z
The sensitivity conjecture has now been proved by Hao Huang: https://arxiv.org/abs/1907.00847.
Yuval Filmus
CC BY-SA 4.0
2019-07-06T08:59:40.527Z
@YuvalFilmus Sensitivity conjecture follows as a consequence. So perhaps more consequences hold up.
Turbo
CC BY-SA 4.0
2019-07-07T16:58:43.403Z
@YuvalFilmus $c\leq4$ demonstrated.
Turbo
<cc.complexity-theory><big-picture><boolean-functions><survey>
Sensitivity-Block sensitivity conjecture - Implications
Turbo
# Sensitivity-Block sensitivity conjecture - Implications

(Asked by: username_0 on 2014-12-05)

Let $f$ be a boolean function with sensitivity $s(f)$ and block sensitivity $bs(f)$.

The Sensitivity-Block sensitivity conjecture conjecture states that there is a $c>0$ such that $\forall f,\mbox{ }bs(f)\leq s(f)^c$.

What are the implications of the truth and falsehood of this conjecture?

Please quote references as well.

**Tags:** cc.complexity-theory, big-picture, boolean-functions, survey
> **Comments:**
> **username_1**: Please consider making the question and its answer more useful by providing definitions of the terms sensitivity and block sensitivity.  
> **username_2**: The sensitivity conjecture has now been proved by Hao Huang: https://arxiv.org/abs/1907.00847.  
> **username_0**: @YuvalFilmus Sensitivity conjecture follows as a consequence. So perhaps more consequences hold up.  
> **username_0**: @YuvalFilmus $c\leq4$ demonstrated.  

---

## 2 answers

### Answer by username_2 on 2014-12-05. Score: 13

Here is what [Scott Aaronson](http://www.scottaaronson.com/blog/?p=453) has to say on the subject:

> What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity measures: the decision-tree complexity of $f$, the certificate complexity of $f$, the randomized query complexity of $f$, the quantum query complexity of $f$, the degree of $f$ as a real polynomial, you name it. So if, as is conjectured, sensitivity and block-sensitivity are polynomially related, then sensitivity—arguably the most basic of all Boolean function complexity measures—ceases to be an outlier and joins a large and happy flock.

Checking other relevant literature doesn't offer any other compelling implications:

* [Nisan and Szegedy](http://link.springer.com/article/10.1007%2FBF01263419) describe the question but offer no motivation at all.
* [Kenyon and Kutin](http://traell.cs.uchicago.edu/files/tr_authentic/TR-2001-22.ps) mention that is is a "natural open question".
* [Gotsman and Linial](http://www.sciencedirect.com/science/article/pii/0097316592900608) give a somewhat contrived equivalent problem (Conjecture 5.33 on page 18 of the following paper).
* [P. Hatami, Kulkarni and Pankratov](http://theoryofcomputing.org/articles/gs004/gs004.pdf), in their comprehensive survey on the problem, also offer no motivation, but they have several equivalent formulations. For example, the sensitivity conjecture is equivalent to the conjecture that the parity decision complexity of a function is polynomially bounded by the sensitivity. Conjecture 5.31 on page 17, due to Shi, is one reformulation that doesn't mention sensitivity at all.
* [Ambainis, Bavarian, Gao, Mao, Sun and Zao](http://eccc.hpi-web.de/report/2014/152/) state that the conjecture "originates from the theory of complexity measures of Boolean functions and
  decision tree complexity", and generally offer the same type of motivation as Scott Aaronson does. Their recent preprint is the last word on the conjecture (as of December 2014).


---

### Answer by username_3 on 2014-12-15. Score: 5

As I understand it, the original motivation was to study CREW PRAM (consecutive read exclusive write parallel RAM) model. In this model, several processors compute a function with shared memory access, but with no write conflicts. [Stephen Cook and Cynthia Dwork](http://dl.acm.org/citation.cfm?doid=800070.802196) and Rudiger Reischuk ("A lower time-bound for parallel random access machines without simultaneous
writes.") showed that $\Omega( \log(s(f)) )$ is a lower bound on the number of steps required to compute $f$ on CREW PRAM. Let $CREW(f)$ denote the minimum number of steps required to compute $f$ in CREW PRRAM. Thus, Cook, Dwork, and Reischuk showed that

$CREW(f) = \Omega(\log s(f))$

Later, [Noam Nisan](http://dl.acm.org/citation.cfm?doid=73007.73038) tweaked the definition of sensitivity to *characterize* $CREW(f)$ up to constant multiplicative factors. The tweaked definition is, of course, block sensitivity. I.e.,

$CREW(f) = \Theta(\log bs(f))$

The natural question then arises whether $CREW(f) = O(\log s(f))$? This is essentially the sensitivity conjecture.

Whether nowadays the implication of sensitivity giving a tight characterization of $CREW(f)$ is compelling or not - I cannot judge. As pointed out in another response, it turned out that block sensitivity is included in a large class of polynomially related complexity measures, while sensitivity is not known to belong to that class.


---

