11 the Sensitivity Conjecture

• Complexity in CS: P, NP, PSPACE

Parameterized complexity:

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

You can always write $f$ as a polynomial of degree $⩽n$. Hence $\mathrm{deg}f$ is a complexity measure.

Approximate $\mathrm{deg}(f)$. Let $B_1,\cdots ,B_s\subseteq [n]$ be disjoint, $s$ maximal such that $f(x\oplus B_i)\ne f(x)$. Then define block sensitivity as $s$, denoted by $bs(f)$. Define sensitivity as $|B_i|$, denoted by $s(f)$.

You can show things like $s(f)⩽bs(f)⩽s(f{)}^{10}$. In general, one can show that all of these natural complexity measures are polynomially related.

bla

For many decades, $s(f)$ has not known to be polynomially equivalent to all other “natural” complexity measures. This problem is equivalent to the following one.

Chang, Furedi, Grahau, Segmour, 1988

Show that for any $Y\subseteq \{0,1{\}}^n$, $|Y|=2^{n-1}+1$, the maximal degree of the induced subgraph $H$ of $Q_n$, denoted by $\Delta (H)$, is at least $\sqrt{n}$, where $Q_n$ is a regular bipartite graph.

Recall that

• $\alpha (Q_n)=|V(Q_n)|/2=2^{n-1}$.
• Ratio bound: $\alpha (Q_n)⩽|V(Q_n)|/(1-\frac{d}{-d})=2^{n-1}$.

\begin{proof} It is proved by Hao Huang in 2019.

Define $A_1=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$. Recursively, define the matrix

$$A_n=\left(\begin{array}{cc}{A}_{n-1}& I\\ I& -A_{n-1}\end{array}\right).$$

Note that $(A_n{)}_{xy}\ne 0$ iff $x\sim y$. Clearly, $A_1^2=I$. By induction,

$$A_{n+1}^2=\left(\begin{array}{cc}{A}_n^2+I& 0\\ 0& A_n^2+I\end{array}\right)=(n+1)I.$$

Thus $A_n$ has eigenvalues $\sqrt{n}$ and $-\sqrt{n}$ with multiplicity $2^{n-1}$ each. Now let $v=(v_1,\cdots ,v_{n+1})$ be an eigenvector $\sqrt{n}$. We claim that $\Delta (H)⩾\sqrt{n}$.

WLOG suppose that $|(v{)}_1|=\max |v_i|=1$. Then

$$|\sqrt{n}|=|\sqrt{n}{v}_1|=|(A_{n}v{)}_1|=|\sum _{j\sim 1}{A}_{1j}{v}_j|=\sum |A_{ij}||v_1|=\sum _{j\sim 1}1⩽\Delta (H).$$

Now we finish the proof. \end{proof}

Remark. By interlacing, the spectrum of $A_n$ restricted to $H$ has an eigenvalue $\sqrt{n}$

$${\lambda }_1(A_H)⩾{\lambda }_{2^{n-1}}(A_n)=\sqrt{n}.$$

Lower Bounds on ${\lambda }_2$

Proposition

Let $\Gamma$ be a $d$-regular graph on $n$ vertices. Then

• $({\lambda }_n+{\lambda }_2^2)n+2(d-{\lambda }_2)({\lambda }_2-{\lambda }_n)⩾0$;
• $({\lambda }_2+{\lambda }_n^2)n+2(d-{\lambda }_n)(-{\lambda }_n)⩾0$.

Say ${\lambda }_2,{\lambda }_n=o(d)$, ${\lambda }_n\gg {\lambda }_2$, $d=o(n)$, then $({\lambda }_n+{\lambda }_2^2)n+2d(-{\lambda }_n)\gtrsim 0$.

\begin{proof} 这个证明非常之长，我不想写了。 \end{proof}

Raty, Sadahov, Tomon

$${\lambda }_2⩾{\left(\frac{ϵ}{4}\right)}^{1/3}{d}^{1/3}-1$$

for $n^{3/4}<d<(1/2-ϵ)n$.

They did also show ${\lambda }_2⩾\sqrt{d}/2(1-o(1))$ if $1⩽d⩽n^{2/3}$; ${\lambda }_2⩾n/2d-1$ fir $n^{2/3}⩽d⩽n^{3/4}$.