A nearly-$4\log n$ depth lower bound for formulas with restriction on top

Here we give a concise description of the proof idea of Theorem 1.6. The whole proof strategy is similar to that in [MS22], we call such strategy as a double-measurement argument, a generalized form of the double-counting argument. One crucial component in such argument is the notion of well-mixed set of functions, and our improvement is mainly due to the simplification and improvement for such well-mixed set of functions.

Let $\mathcal{G}$ be the set of all functions from $\{0,1\}^{n}\rightarrow\{0,1\}^{n}$. Now given a hard function $f:\{0,1\}^{n}\rightarrow\{0,1\}$, we want to show there exists a function $g\in\mathcal{G}$, such that if $f\boxplus g$ can be computed by a formula $\phi_{g}=\bigwedge_{i=1}^{2^{\alpha n}}\phi_{g,i}$, there must be a sub-formula $\phi_{g,i}$ such that $\mathsf{L}(\phi_{g,i})$ is large. To show this, Mihajlin and Sofronova defined a sub-additive measure $\mu$ for Boolean functions of two arguments and $\mu(f\boxplus g)$ is large, thus by averaging, for every $g$, there exists some $i_{g}$ such that $\mu(\phi_{g,i_{g}})$ is large enough. Note that for every $g,i_{g}$, $\phi_{g,i_{g}}$ computes some function $h_{g,i_{g}}$, and let $\mathcal{H}$ be the set of all such functions $h_{g,i_{g}}$. If the size of $\mathcal{H}$ is large, by a standard counting argument, there must be a hard function $h\in\mathcal{H}$ as required. But $\mathcal{H}$ may be a small set, to prevent this, we need to show for every $h\in\mathcal{H}$, there only exists a small subset of $\mathcal{G}_{h}\subseteq\mathcal{G}$ such that for every $g\in\mathcal{G}_{h}$, $h_{g,i_{g}}$ is the same function as $h$. Formally, denote the $\{g|g\in\mathcal{G},h_{g,i_{g}}=h\}$ by $\mathcal{G}_{h}$. Let $h_{\star}$ be the function such that the size of $\mathcal{G}_{h_{\star}}$ is maximum among all $\mathcal{G}_{h}$, it suffices to show $\mathcal{G}_{h_{\star}}$ is a small set. To this end, we need to show an up bound of measurement $\mu(h_{\star})$ in another way and this is why the notion of well-mixed set is involved.

Now consider this function $\mathcal{M}_{f,\mathcal{G}_{h_{\star}}}(x,y)=\bigvee_{g\in\mathcal{G}_{h_{\star}}}f(g(x)\oplus y)$. Let $\mathcal{M}_{f,\mathcal{G}_{h_{\star}}}^{x}$ be the function $\mathcal{M}_{f,\mathcal{G}_{h_{\star}}}$ with the first argument is fixed to be some $x\in\{0,1\}^{n}$, we want to show if the set $\mathcal{G}_{h_{\star}}$ is large, there are many $x$s such that $\mathcal{M}_{f,\mathcal{G}_{h_{\star}}}^{x}$ is almost a constant function, and it eventually implies $\mu(h_{\star})$ is small which contradicts the fact that $\mu(h_{\star})$ is already large. This is essentially the property that Mihajlin and Sofronova wanted for $\mathcal{G}_{h_{\star}}$, or in their terms, $\mathcal{G}_{h_{\star}}$ is well-mixed for function $f$. In their work, Mihajlin and Sofronova used a rather complicated probabilistic method to show that property.

We will show such complication is entirely unnecessary and the well-mixed property could be obtained by a simple counting argument if you choose the function $f$ properly. For convenience, let $N=2^{n}$, now choose a hard function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ such that $\text{density}(f^{-1}(1))=\frac{|f^{-1}(1)|}{N}\geq\delta$, typically, we set $\delta$ to be $\frac{1}{4}$. Note that given any fixed $x$, $\mathcal{M}_{f,\mathcal{G}_{h_{\star}}}^{x}(y)=1$ if there is a function $g\in\mathcal{G}_{h_{\star}}$ such that $(g(x)\oplus y)\in f^{-1}(1)$. Given any $x\in\{0,1\}^{n}$, denote the set $\{z|\exists g\in\mathcal{G}_{h_{\star}},g(x)=z\}$ by $\mathcal{G}_{h_{\star}}(x)$. Similarly, given $x,y\in\{0,1\}^{n}$, we denote the set $\{z|\exists g\in\mathcal{G}_{h_{\star}},g(x)\oplus y=z\}$ by $\mathcal{G}_{h_{\star}}(x)\oplus y$. Given an $x$, if $|\mathcal{G}_{h_{\star}}(x)|>N(1-\delta)$, for any fixed $y$, we also have $|\mathcal{G}_{h_{\star}}(x)\oplus y|>N(1-\delta)$, since for any fixed $y$, $z\oplus y$ is permutation function of $z$. When $|\mathcal{G}_{h_{\star}}(x)\oplus y|>N(1-\delta)$, $(\mathcal{G}_{h_{\star}}(x)\oplus y)\cap f^{-1}(1)$ is not empty, this means there exists $g\in\mathcal{G}_{h_{\star}}$ such that for that $x$, $f(g(x)\oplus y)=1$.

Now we say $x$ is bad, if $|\mathcal{G}_{h_{\star}}(x)|\leq N(1-\delta)$. If $\mathcal{G}_{h_{\star}}$ is a dense subset of $\mathcal{G}$, the number of bad $x$s is small. Assume the size of $\mathcal{G}_{h_{\star}}$ is (at least) $|\mathcal{G}|\cdot(1-\delta)^{P}$, then there are at most $P$ bad $x$s. If not, the number of functions in $\mathcal{G}_{h_{\star}}$ is less than

which is a contradiction. This means, given any $x$ which is not bad, the function $\mathcal{M}_{f,\mathcal{G}_{h_{\star}}}^{x}(y)=1$ for any $y$, thus $\mathcal{M}_{f,\mathcal{G}_{h_{\star}}}^{x}$ is a constant function. This eventually implies $\mu(h_{\star})$ is small which leads to the desired contradiction. Finally, since $\mathcal{G}_{h_{\star}}$ has to be a small set, the set $\mathcal{H}$ must be a large set of functions which contains a hard function $h\in\mathcal{H}$ as required. See more details in Lemma 3.2 and Theorem 3.3.

Besides Mihajlin and Sofronova’s work, we note that Bathie and Williams [BW24] established a super-$3\log n$ depth lower bound against uniform circuits consisting of only NAND gates. Since their result is against uniform circuits, it is incomparable to ours. They also pointed out that results similar to Mihajlin and Sofronova’s work could be obtained from average-case lower bounds [KRT17] via restriction-based techniques but they didn’t provide further details. In a personal communication, Meir [Mei24] pointed out that results similar to Mihajlin and Sofronova’s work can also be obtained via techniques from communication complexity but it is not clear whether such results are as tight as ours.