Submit progress

on The Strong Sensitivity Conjecture

The statement

Let $n$ be a natural number. A Boolean function on $n$ variables is a function $f : \{0,1\}^n \to \{0,1\}$ . For $x \in \{0,1\}^n$ and $B \subseteq \{1, \ldots, n\}$ , let $\operatorname{flip}(x, B)$ denote the element of $\{0,1\}^n$ obtained from $x$ by flipping all bits whose indices lie in $B$ . The local sensitivity of $f$ at $x$ , denoted $s(f, x)$ , is the number of indices $i \in \{1, \ldots, n\}$ such that $f(\operatorname{flip}(x, \{i\})) \neq f(x)$ . The sensitivity of $f$ , denoted $s(f)$ , is the maximum of $s(f, x)$ over all $x \in \{0,1\}^n$ . A collection $\mathcal{B}$ of nonempty subsets of $\{1, \ldots, n\}$ is called a valid block configuration for $f$ at $x$ if the sets in $\mathcal{B}$ are pairwise disjoint and $f(\operatorname{flip}(x, B)) \neq f(x)$ for every $B \in \mathcal{B}$ . The local block sensitivity of $f$ at $x$ , denoted $\operatorname{bs}(f, x)$ , is the maximum cardinality of a valid block configuration for $f$ at $x$ . The block sensitivity of $f$ , denoted $\operatorname{bs}(f)$ , is the maximum of $\operatorname{bs}(f, x)$ over all $x \in \{0,1\}^n$ . Does $\operatorname{bs}(f) \leq s(f)^2$ hold for every Boolean function $f$ on $n$ variables?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.