Sensitivity-Block sensitivity conjecture - Implications

Question

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.

Answer 1

Here is what Scott Aaronson 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 describe the question but offer no motivation at all.
• Kenyon and Kutin mention that is is a "natural open question".
• Gotsman and Linial give a somewhat contrived equivalent problem (Conjecture 5.33 on page 18 of the following paper).
• P. Hatami, Kulkarni and Pankratov, 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 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 2

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 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 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.