Lower Bounds Beyond DNF of Parities

We start from an empty CNF formula $C$ and gradually add clauses to it. Consider any $y\notin A$. As it is not a $k$-limit of $A$, there exists a set $I\in \left(\genfrac{}{}{0pt}{}{[n]}{k}\right)$ such that $y_I\ne a_I$ for any $a\in A$. Let us add into $C$ a clause $D={\bigvee }_{i\in I}{x}_i^{1-y_i}$. This clause evaluates to $0$ on $y$ and evaluates to $1$ on any $a\in A$.

We repeat the procedure for every $y\notin A$. The resulting CNF evaluates to $0$ on every $y\notin A$ and evaluates to $1$ on any $a\in A$, which proves the claim. $\mathrm{⊲}$

Note that a $k\text{-}\text{CNF}$ over $n$ variables has at most ${(2n)}^k=2^{O(k\log n)}$ clauses. The standard assumption for ${\mathrm{𝖠𝖢}}^0$ is that the bottom fan-in of the circuit is bounded by the logarithm of its size, so $k$-limits are a tool that helps to prove lower bounds of the form $2^k$. To be more precise, it follows from Claim 6 that if a set $A$ has a $k$-limit outside of $A$, then any CNF recognising it should have size $2^{\mathrm{\Omega }(k)}$, and it follows from Claim 7 that for any set $A$ containing all of its $k$-limits there is a CNF of size $2^{O(k\log n)}$ recognising $A$. So there is a multiplicative gap of $\log n$ in the exponent between related lower bound and upper bound. In most cases, this is a negligible difference, but for some examples this might be important: for example, Maj function has a lower bound of $2^{\mathrm{\Omega }\left(\sqrt{n}\right)}$ in depth-$3$ ${\mathrm{𝖠𝖢}}^0$ and an upper bound of $2^{O\left(\sqrt{n}\log n\right)}$ in the same model. Proving a $2^{\omega (\sqrt{n})}$ lower bound for Maj would beat all state-of-the-art lower bounds for depth-$3$ ${\mathrm{𝖠𝖢}}^0$ circuits.

Let $x$ be the $k$-parity limit of $A$. Suppose $C$ rejects $x$. Then there exists a particular $\text{Or}\circ \text{Xor}$ subcircuit of $C$ (denote it by $C^{\prime }$) such that $C^{\prime }(x)=0$. Let $L$ be the affine subspace of co-dimension $k$ defined by zeroes of $C^{\prime }$. Then $x\in L$, and therefore $A\cap L\ne \mathrm{\varnothing }$. Then for some $y\in A$ it holds that $C^{\prime }(y)=0$ and therefore $C(y)=0$, which is a contradiction with the assumption that $C$ accepts the whole $A$. $\mathrm{⊲}$

As there are much more linear subspaces of co-dimension $k$ than clauses of width $k$, while we can prove the analogue of Claim 7 for $k$-parity limits, the resulting circuit would have huge size, so this approach would not give a meaningful size upper bound. One could ask a question: is it possible to prove a reasonable upper bound from non-existence of “outer” $k$-parity limits?

For proving lower bounds against ${\mathrm{𝖠𝖢}}^0\circ \text{Xor}$, it is sufficient to find $k$-parity limits only with respect to a fixed set of linear forms present in a circuit (subcircuit), but it would be interesting to know if the more general statement is true. Again, the existence of a $k$-parity limit with respect to a fixed set of linear forms is a necessary condition for a lower bound.

The proof of the next claim is, again, analogous to Claim 6.

Here $𝒮$ can be a collection of all affine subspaces of co-dimension $k$, or it can be a smaller family of subspaces that still contains all linear systems used in a ($k$-$\text{CNF})\circ \text{Xor}$. In other words, as the number of linear systems used in a circuit is bounded by its size, one can relax the definition of a $k$-parity limit to be able to fool only these linear systems. One can also prove a variant of completeness for this weaker notion of $k$-parity limits analogous to Claim 7.

Exponential size $\text{Or}\circ ({\mathrm{\Pi }}^0\circ 𝔹)$, in particular, can use exponential number of different linear forms, with the restriction that inside each $\text{CNF}\circ \text{Xor}$ subcircuit there are only $n$ different linear forms. Our results can be seen as finding $k$-parity limits under these restrictions on the model. In top-down language, the extra Or on top symbolises that the first step down in the proof is oblivious to the actual parity gates that are used in the circuit. Now, just two such oblivious steps would imply lower bounds for $\vee \circ \wedge \circ \vee \circ \text{Xor}$.

When comparing top-down lower bounds for plain ${\mathrm{𝖠𝖢}}^0$ and $\text{Or}\circ ({\mathrm{\Pi }}^0\circ 𝔹)$, the most important difference (and our main technical contribution) is the following: for $\text{Or}\circ ({\mathrm{\Pi }}^0\circ 𝔹)$, we should be able to construct sets such that we can find their $k$-limits after any change of basis in ${𝔽}_2^n$. Note that the hard functions in this case should be uncorrelated with affine subspaces, which, in particular, is not true for Xor function: after the appropriate change of basis, we could encode the value of the function in the first bit of the string in the new basis.

This seems like a natural step towards fully adapting the top-down approach for circuits with Xor gates. We discuss this further in Section 4.

Suppose that there exists $x^{\prime }$ with $x_{[n]\setminus R}^{\prime }=x_{[n]\setminus R}$ that is not a $q$-limit for $X$, i.e. there exists a set $S\subseteq [n]$ of size $q$ such that for every $y\in X$ we have $x_S^{\prime }\ne y_S$. Observe that $(S\setminus R,x_{S\setminus R})$ is then a certificate for $R$: indeed for any $b\in {\{0,1\}}^R$ that agrees with $x_{S\cap R}^{\prime }$ we have that for every $y\in X$ we have $y_R\ne b$. $◀$

Suppose that $X$ is not $\theta$-linearly spread in ${\{0,1\}}^n$. Then consider the affine subspace of largest co-dimension $A$ that witnesses the lack of $\theta$-spreadness of $X$: suppose that $A$ has co-dimension $\mathrm{\ell }$ then we have $|X\cap A|/|X|>{\theta }^{-\mathrm{\ell }}$.

We claim then that $X\cap A$ is $\theta$-lineraly spread in $A$. Indeed, suppose that it is not, i.e. there exists an affine subspace $B$ of $A$ of co-dimension ${\mathrm{\ell }}^{\prime }$ (in $A$) such that $|X\cap B|/|X\cap A|>{\theta }^{-{\mathrm{\ell }}^{\prime }}$. Then $|X\cap B|/|X|>{\theta }^{-{\mathrm{\ell }}^{\prime }-\mathrm{\ell }}$ which contradicts the maximality of the co-dimension of $A$.

Now it remains to bound the co-dimension of $A$. On the one hand

On the other hand ${\mathrm{Pr}}_{𝒙\sim X}[𝒙\in A]>{\theta }^{-\mathrm{\ell }}$. Hence $d>\mathrm{\ell }(1-{\log }_2\theta )$. The lower bound on $|X\cap A|$ follows. $◀$

Suppose for contradiction that $C^{-1}(1)=\left(\genfrac{}{}{0pt}{}{[n]}{n/2}\right)$, $N\le 2^{\gamma \sqrt{n}}$ where $\gamma$ is a constant to choose later. Since $C^{-1}(1)={\bigcup }_{i\in [N]}{C}_i^{-1}(1)$, there exists $i_0\in [N]$ such that $|C_{i_0}^{-1}(1)|\ge |\left(\genfrac{}{}{0pt}{}{[n]}{n/2}\right)|\cdot 2^{-\gamma \sqrt{n}}$.

Thus, there exists a CNF $D$ and a full-rank linear transformation $A$ such that $X≔{(D\circ A)}^{-1}(1)$ has size at least $\left(\genfrac{}{}{0pt}{}{n}{n/2}\right)\cdot 2^{-\gamma \sqrt{n}}\ge 2^{n-\gamma \sqrt{n}-\log n}$ and $X\subseteq \left(\genfrac{}{}{0pt}{}{[n]}{n/2}\right)$. Let us identify the linear transformation $A$ with the matrix in ${\{0,1\}}^{n\times n}$ defining it: $A(x)≔Ax$.

First we apply Lemma 17 to the set $X$ with the parameter $\theta =\sqrt{2}$. We get that there exists an affine space $B$ of co-dimension at most $2(\gamma \sqrt{n}+\log n)$ such that $X\cap B$ is $\theta$-linearly spread in $B$ and $|X\cap B|\ge |X|/2^{\gamma \sqrt{n}+\log n}$.

Applying Lemma 13 to the set $A(X\cap B)=\{Ax\mid x\in X\cap B\}$ with $q=5\gamma \sqrt{n}$ we get:

Pick $\gamma$ such that this probability is at least $0.9$. That is, with probability $0.9$ for a pair $(𝒙,𝒊)\sim (X\cap B)\times [n]$ we have by Lemma 15 that $A𝒙+e_{𝒊}$ (where $e_i=0^{i-1}{10}^{n-i}$) is a $q$-limit of the set $A(X\cap B)$. In order to invoke Lemma 8 we need to find many $q$-limits in $D^{-1}(0)$, i.e., outside of $A(X)$.

Suppose that $Ax+e_i\in A(X)$ for some $(x,i)\in (X\cap B)\times [n]$. Equivalently $x+A^{-1}{e}_i\in X$. Then in particular $x+A^{-1}{e}_i\in \left(\genfrac{}{}{0pt}{}{[n]}{n/2}\right)$. Since $x\in X\subseteq \left(\genfrac{}{}{0pt}{}{[n]}{n/2}\right)$, this is only possible if $A^{-1}{e}_i$ has even hamming weight and in that case implies that $⟨x,A^{-1}{e}_i⟩=(|\{j\in [n]\mid {(A^{-1}{e}_i)}_j=1\}|/2)mod2≕c_i$.

In other words, if adding $A^{-1}{e}_i$ to $x$ preserves its Hamming weight $\frac{n}{2}$, it means that exactly half of the indices of $1$-coordinates in $A^{-1}{e}_i$ match up with indices of $1$-coordinates in $x$, which fixes the value of $⟨x,A^{-1}{e}_i⟩$ to a constant $c_i$.

Now consider the affine subspace $B_i^{\prime }≔\{y\in B\mid ⟨y,A^{-1}{e}_i⟩=c_i\}$. If $A^{-1}{e}_i\in B^{\perp }≔\{x\in {\{0,1\}}^n\mid \forall y\in B,⟨x,y⟩\text{ is fixed}\}$ ($B^{\perp }$ is the span of all linear constraints defining $B$), then $B_i^{\prime }=B_i$ or $B^{\prime }=\mathrm{\varnothing }$, otherwise $B_i^{\prime }$ has co-dimension $1$ in $B$. Let $E$ be the event when $A^{-1}{e}_{𝒊}$ is in $B^{\perp }$. We then have

Since the co-dimension of $B$ (equivalently the dimension of $B^{\perp }$) is at most $2(n^{\gamma }+\log n)$ and $A^{-1}{e}_1,\mathrm{\dots },A^{-1}{e}_n$ are linearly independent, $\mathrm{Pr}[E]\le 2(\gamma \sqrt{n}+\log n)/n=o(1)$. On the other hand since $A𝒙+e_{𝒊}\in A(X)$ implies that $𝒙\in B_{𝒊}^{\prime }$ and $X\cap B$ is $\theta$-linearly spread in $B$ we get $\mathrm{Pr}[A𝒙+e_{𝒊}\in A(x)\mid \neg E]\le 1/\sqrt{2}.$ Therefore $\mathrm{Pr}[A𝒙+e_{𝒊}\notin A(X)\wedge A𝒙+e_{𝒊}\text{ is a }q\text{-limit of }A(X\cap B)]\ge 0.9-1/\sqrt{2}-o(1),$ so there are $\mathrm{\Omega }(|X\cap B|)$ $q$-limits to $A(X\cap B)$ outside of $A(X)$, hence by Lemma 8 we get that

$◀$

We show that either $N\ge 2^{n^{\gamma }}$ or one of the CNFs $C_1,\mathrm{\dots },C_N$ has size at least $2^{n^{\gamma }}$, which yields the claim. Suppose . Then there exists $C_i=D_i\circ A_i$ such that $|C_i^{-1}(1)|\ge |f^{-1}(1)|/2^{n^{\gamma }}\ge 2^{n-2n^{\gamma }}$.

Let $X≔{(D_i\circ A_i)}^{-1}(1)$. For the set $A_i(X)$ we apply Lemma 14 with the following parameters:

• $\mathrm{■}$

  the density loss $t=2n^{\gamma }$;

• $\mathrm{■}$

  the size of certificate $q=\alpha n^{\gamma }$;

• $\mathrm{■}$

  the size of the unpredictable block $r=\beta n^{\gamma }$.

The constants $\alpha ,\beta$ are to be chosen later. It follows that with probability $1-O(n^{3\gamma -1})=1-o(1)$ for $𝒙\sim X$ and $𝑹\sim \left(\genfrac{}{}{0pt}{}{[n]}{r}\right)$ there is no certificate of size $q$ in $A_i𝒙$ for $𝑹$. Hence, by Lemma 15 all elements of

are $q$-limits of $A_i(X)$ with probability $1-o(1)$. Let $E$ be the set of pairs $x,R\in X\times \left(\genfrac{}{}{0pt}{}{[n]}{r}\right)$ for which this holds.

For $(x,R)\in E$ consider the set $A_i^{-1}(L_{x,R})$. $L_{x,R}$ is an $r$-dimensional affine subspace of ${\{0,1\}}^n$, thus $A_i^{-1}(L_{x,R})$ is as well. As $f$ is an affine disperser, there is an input $y\in A_i^{-1}(L_{x,R})\cap f^{-1}(0)$, hence $A_i\cdot y$ is not in $X$ and is a $q$-limit of $X$.

Now we need to count the number of $q$-limits we got in order to invoke Lemma 8. Let $g:E\to {\{0,1\}}^n$ be the function mapping $(x,R)$ to $A_i\cdot y$ (to an arbitrary one, if there are several). Let us upper bound $|g^{-1}(z)|$ for an arbitrary $z\in {\{0,1\}}^n$. Suppose $g(x,R)=z$, let $y={(A_i)}^{-1}z$, then $x_{[n]\setminus R}=y_{[n]\setminus R}$, hence, there are at most $2^r\cdot \left(\genfrac{}{}{0pt}{}{[n]}{r}\right)$ such preimages. Thus we get $|E|/(2^r\left(\genfrac{}{}{0pt}{}{[n]}{r}\right))=|X|/2^r$ $q$-limits in total. Therefore by Lemma 8 we get that $|D_i|\ge (1-o(1))2^{n-2n^{\gamma }}/(2^r\cdot 2^{n-q})\ge 2^{q-r-2n^{\gamma }-1}\ge 2^{(\alpha -\beta -2)n^{\gamma }-1}$. Hence for any $\alpha >\beta +2$ we get the desired bound. $◀$

Suppose for contradiction that the total size of all $D_i$ is at most $2^{n^{\epsilon }}$ for $\epsilon =o(1/d)$. Then let us pick $𝜶\sim {\{0,1\}}^n$ and apply the restriction $y=𝜶$ to $C$. Then ${C|}_{y=𝜶}$ computes the function ${\text{Xor}}_{𝜶}≔{⨁}_{i\in [n]:{𝜶}_i=1}{x}_i$ and has the same form as before, disjunction of compositions of constant-depth circuits with affine transformations.

Let $D_i^{\prime },A_i^{\prime }$ be such that ${C|}_{y=𝜶}={\bigvee }_{i\in [N]}{D}_i^{\prime }\circ A_i^{\prime }$. Since ${\text{Xor}}_{𝜶}$ is balanced, there exists $i_0\in [N]$ such that $|{(D_{i_0}^{\prime }\circ A_{i_0}^{\prime })}^{-1}(1)|\ge 2^{|\alpha |-1-n^{\epsilon }}$. On the other hand ${(D_i^{\prime }\circ A_i^{\prime })}^{-1}(0)\supseteq {\text{Xor}}_{𝜶}^{-1}(0)$ for all $i\in [N]$. Then applying ${(A_{i_0}^{\prime })}^{-1}$ to $D_{i_0}^{\prime }\circ A_{i_0}^{\prime }$ and to ${\text{Xor}}_{𝜶}$ on the right we get that the circuit ${(D_{i_0}^{\prime })}^{-1}(0)\supseteq {\text{Xor}}_{{𝜶}^{\mathbf{\prime }}}$ where ${𝜶}^{\mathbf{\prime }}=𝜶\cdot {(A_{i_0}^{\prime })}^{-1}$ and since $A_{i_0}^{\prime }$ has full rank $|{(D_{i_0}^{\prime })}^{-1}(1)|=|{(D_{i_0}^{\prime }\circ A_{i_0}^{\prime })}^{-1}(1)|\ge 2^{|\alpha |-1-n^{\epsilon }}$.

Now observe that
$$\mathrm{Pr}[|{𝜶}^{\prime }|\le \sqrt{n}]=\mathrm{Pr}[𝜶\text{ is a linear combination of }\le \sqrt{n}\text{ rows of }{(A_{i_0}^{\prime })}^{-1}]\le N\cdot \left(\genfrac{}{}{0pt}{}{|\alpha |}{\sqrt{n}}\right)/2^n=o(1).$$

Hence, there exists a depth-$d$ de Morgan circuit $D=D_{i_0}^{\prime }$ that computes parity ${\text{Xor}}_{{\alpha }_0}$ on $\sqrt{n}$ bits correctly on all $0$-inputs and on at least $2^{-n^{\epsilon }}$-fraction of $1$-inputs. Then let ${𝒚}_1,\mathrm{\dots },{𝒚}_M\sim {\text{Xor}}_{{\alpha }_0}^{-1}(0)$ be independent random variables. Then the depth-$(d+1)$ circuit $E_{𝒚}(x)≔{\bigvee }_{i\in [M]}D(x\oplus {𝒚}_i)$ computes the value of ${\text{Xor}}_{{\alpha }_0}$ correctly on an input $x$ with probability $1-{(1-2^{-n^{\epsilon }})}^M$, which exceeds $1-2^{-n}$ for $M>3n\cdot 2^{n^{\epsilon }}$, hence, there exists a setting of $y=y_1,\mathrm{\dots },y_M$ such that $E_y$ computes ${\text{Xor}}_{{\alpha }_0}$. Thus by [18] the size of $E_y$ is at least $2^{n^{\mathrm{\Omega }(1/d)}}$ which means that $\epsilon =\mathrm{\Omega }(1/d)$ which is a contradiction. $◀$