Submit progress

on The degree--sensitivity exponent ($C_{37}$)

The statement

Let $f$ be a Boolean function on $n$ bits, i.e.

f:\{0,1\}^n \to \{0,1\}

with $n\ge 2$ . For $x\in$ {0,1}^n and $1\le i\le n$ , let $x^{(i)}$ be $x$ with the $i$ -th bit flipped.

The (pointwise) sensitivity of $f$ at $x$ is

s(f)(x):=\sum_{i=1}^n |f(x)-f(x^{(i)})|,

and the (max) sensitivity is

s(f):=\max_{x\in\{0,1\}^n} s(f)(x).

Let $\deg(f)$ be the degree of the unique multilinear polynomial over $\mathbb{R}^{n}$ that agrees with $f$ on {0,1}^n.

Define the degree--sensitivity exponent

C_{37}:=\sup \frac{\log \ (s(f))}{\log (\deg(f))},

where the supremum ranges over all $n\geq 2$ and all Boolean functions $f$ on {0,1}^n with $\deg(f)>1$ .

Equivalently, $C_{37}$ is the supremum over exponents $\alpha>0$ such that there exists a Boolean function $f$ of degree at least 2 with

s(f)\ge (\deg(f))^{\alpha}.

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.