The Switching Lemma shows
what the Switching Lemma cannot prove:
an unconditional natural-proofs barrier
January 01, 1970
The natural-proofs barrier of Razborov and Rudich (JCSS’97) begins with the striking observation that all known lower-bound proofs follow a certain pattern: when showing that a function \(F\) is hard, along the way the proof provides us with a distinguisher, namely, an efficient algorithm which, when given a truth-table \(f\) as input, can distinguish the case when \(f\) is an easy function from the case when \(f\) is a random function. They called such lower-bound proofs natural proofs. They then showed that under standard cryptographic assumptions, natural proofs cannot show, e.g., superpolynomial lower-bounds against Boolean circuits.
By comparison, in the world of constant-depth circuits we do have strong lower-bounds. Håstad’s celebrated Switching Lemma gives a sharp lower bound of \(2^{\Omega(n^{1/(d - 1)})}\) for depth-\(d\) circuits with gates of unbounded fan-in that compute the Parity function. This remains the best known lower bound against \({\mathsf {AC}}_0\) for any explicit function. Following Razborov and Rudich, it can be shown that under a suitable cryptographic assumption, natural proofs cannot prove a significantly better lower bound, such as of \(2^{n^{c/d}}\) for some large constant \(c\).
In this paper we revisit the natural-proofs barrier from an unconditional perspective. We focus on \({\mathsf {AC}}_0\)-natural proofs, namely natural proofs whose associated distinguisher is itself computable by an \({\mathsf {AC}}_0\) circuit. Razborov and Rudich already observed that lower bounds based on the Switching Lemma are \({\mathsf {AC}}_0\)-natural. We begin by showing that this is also true for most known lower-bound techniques against constant-depth circuits.
We then establish an unconditional barrier for such proofs. By localizing the Trevisan–Xue pseudorandom generator, we construct a pseudorandom function computable by depth-\(d\) circuits of size \(2^{n^{O(1/d)}}\), that unconditionally fools \({\mathsf {AC}}_0\) distinguishers of arbitrary constant depth. It follows, for example, that no \({\mathsf {AC}}_0\)-natural proof can prove a lower bound greater than \(2^{n^{7/(d-5)}}\) against depth-\(d\) circuits.
The result is not tight: the ideal barrier would match the \(2^{\Theta(n^{1/(d-1)})}\) Switching-Lemma frontier, instead of having \(7/(d-5)\) in the power of \(n\). Nevertheless, it gives an unconditional natural-proofs barrier in the same qualitative regime. The proof has a striking self-referential aspect: the proof of security of the Trevisan–Xue generator crucially relies on the Switching Lemma, and so the Switching Lemma has been used to show that \({\mathsf {AC}}_0\)-natural proofs, such as the Switching Lemma itself, cannot prove \({\mathsf {AC}}_0\) lower bounds significantly better than the state of the art.
A central problem in circuit complexity is to prove lower bounds for explicit functions against constant-depth circuits. By constant-depth circuits we mean “\({\mathsf {AC}}_0\)” circuits, i.e., circuits with unbounded-fan-in AND and OR gates, together with NOT gates. For depth-\(d\) circuits, Håstad’s Switching Lemma [1] gives lower bounds of size \(2^{\Omega(n^{1/(d-1)})}\) for the Parity function, and this bound is tight for Parity. The challenge is to prove a stronger lower bound for some other explicit function.
Even for depth \(3\), improving the known frontier is a central open problem [2], [3]. Because of a depth reduction result by Valiant [4], a sufficiently strong depth-\(3\) lower bound, namely a lower bound of size \(2^{\omega(n/\log\log n)}\), would imply a super-linear lower bound for log-depth circuits. Thus progress on depth-\(3\) lower bounds would have consequences beyond constant-depth complexity itself.
We study this frontier through the lens of the Razborov–Rudich natural-proofs paradigm [5]. Informally, a lower-bound proof, showing that a function \(F\) is “hard”, is called a natural proof, if it identifies a property \(\Phi(\cdot)\) of truth tables satisfying the following:
Usefulness: \(\Phi(F) = 1\) but \(\Phi(f) = 0\) for all “easy” functions \(f\).
Largeness: \(\Phi(f) = 1\) for a noticeable fraction of all functions.
Constructiveness: \(\Phi(f)\) can be efficiently computed when given the truth table of \(f\) as input.
Hence, a useful, large, constructive property \(\Phi\) is an efficient algorithm that distinguishes a random function from every “easy” function. Razborov and Rudich have shown that all circuit lower-bound proofs known at the time are natural proofs, and hence all such lower-bound proofs yield efficient distinguishers. The key observation of Razborov and Rudich was then the following: under standard cryptographic assumptions, we can construct pseudorandom functions (PRFs), namely, distributions over easy functions whose truth tables cannot be distinguished from random truth-tables by any efficient distinguisher. It follows that, under standard cryptographic assumptions, natural proofs cannot prove a lower bound against, say, polynomial-size circuits.
Notice here that this conclusion — better lower-bounds cannot be proven by natural proofs — only follows conditionally: it follows under a certain, unproven cryptographic assumption.
For instance, under the widely believed assumption that sufficiently secure PRFs are computable by polynomial-size log-depth (\(\mathsf{NC}_1\)) circuits, the usual natural-proofs barrier already rules out natural proofs of stronger \({\mathsf {AC}}_0\) lower bounds. This is because of a standard simulation of \(\mathsf{NC}_1\) by depth-\(d\) circuits, which implies that \(\mathsf{NC}_1\)-PRFs of depth \(c \log n\) can also be computed by depth-\(d\) circuits of size \(2^{n^{c/(d-1)}}\). Consequently, conditional on this cryptographic assumption, there is a constant \(c\) such that no natural proof can prove depth-\(d\) lower bounds above \(2^{n^{c/(d-1)}}\).3 However, this does not explain the exact frontier suggested by the Switching Lemma.
Razborov and Rudich have also observed that lower bounds against \({\mathsf {AC}}_0\) circuits have an additional feature: the associated property \(\Phi\) is not merely efficiently decidable, it is actually decidable by a small \({\mathsf {AC}}_0\) circuit. We may call such proofs \({\mathsf {AC}}_0\)-natural. One of our contributions, in 3, is surveying the more recent lower-bounds and showing that this remains essentially true today: most of the known lower-bound proofs against \({\mathsf {AC}}_0\) circuits are in fact \({\mathsf {AC}}_0\)-natural. In particular, lower-bound proofs based on the Switching Lemma are \({\mathsf {AC}}_0\)-natural.
Thus, in the setting of \({\mathsf {AC}}_0\) lower-bounds, the distinguishers arising from \({\mathsf {AC}}_0\)-natural proofs are themselves \({\mathsf {AC}}_0\) circuits. And since unconditional pseudo-random generators fooling \({\mathsf {AC}}_0\) are known (see [7] for a survey of these results), one can speculate whether there exists an unconditional version of the natural-proofs barrier.
Concretely, to rule out \({\mathsf {AC}}_0\)-natural proofs beyond the known depth-\(d\) frontier, one would have to construct pseudo-random functions satisfying two requirements: they should be computable by depth-\(d\) circuits of size near \(2^{n^{{1}/{(d-1)}}}\), and they should fool \({\mathsf {AC}}_0\) distinguishers (of size \(\mathsf{poly}(2^n) = 2^{O(n)}\), or ideally even \(2^{n^{O(1)}}\)) that inspect the full truth table.4 This leads to the following question.
Question 1. For every \(d \ge 3\) does there exist a distribution on functions each computable by depth-\(d\) circuits of size \(2^{O(n^{{1}/{(d-1)}})}\) that fools \(\mathsf{poly}(2^n)\)-size \({\mathsf {AC}}_0\) circuits?
Note that an affirmative answer implies an unconditional natural-proofs barrier in the following sense. Take any property \(\Phi\) of \(n\)-variate Boolean functions that rejects all functions computable by depth-\(d\) circuits of size \(2^{O(n^{1/(d - 1)})}\) while accepting a random function with high probability. Then \(\Phi\) itself cannot be computed by an \({\mathsf {AC}}_0\) circuit of size \(\mathsf{poly}(2^n)\). This would unconditionally explain why techniques such as the Switching Lemma cannot be used to yield stronger lower bounds than the current state of the art.
It should be noted here that Razborov and Rudich [5] have shown an unconditional natural-proofs barrier, specifically showing that no polynomial size \({\mathsf {AC}}_0\)-natural proof can prove a superpolynomial lower bound against polynomial size \({\mathsf {AC}}_0[2]\) circuits. This is based on the Nisan–Wigderson generator [9] that is implementable as a PRF using constant depth polynomial size \({\mathsf {AC}}_0[2]\) circuits and that fools \({\mathsf {AC}}_0\) circuits. More specifically there is a fixed depth \(d\) such that for any constant depth \(d'\) and polynomial (in \(2^n\)) size \(S'\), there is a \({\mathsf {AC}}_0[2]\) PRF of depth \(d\) and size polynomial in \(n\) that fools all depth-\(d'\) size-\(S'\) \({\mathsf {AC}}_0\) circuits. It is natural to ask whether this PRF is also implementable with efficient subexponential size \({\mathsf {AC}}_0\) circuits so that it may have some bearing on our question. The answer is an unsatisfactory yes. The Nisan–Wigderson generator is implementable via depth-\(d\) size-\(2^{n^{O(1/d)}}\) circuits. However, the constant in the double exponent now depends on the depth \(d'\) that we are trying to fool, and this gives us a “weak” \({\mathsf {AC}}_0\)-natural-proofs barrier.
We go over a similar case in more detail: In 4, we will show a very similar weak natural-proofs barrier arising from a simple PRF, whose security follows from Braverman’s theorem. This PRF has better parameters than the \({\mathsf {AC}}_0\) PRF we just sketched (which is based on \({\mathsf {AC}}_0[2]\) PRFs). It will be used in 5 as an important step in our main result, which is a stronger \({\mathsf {AC}}_0\)-natural-proofs barrier.
Our first observation is that Braverman’s theorem [10], which says that polylogarithmic-wise independence fools \({\mathsf {AC}}_0\), already yields a simple pseudo-random function distribution supported on functions computable by circuits of depth \(d\) and size \(2^{n^{O(1/d)}}\). As alluded to above, the constant in the double exponent depends on the depth \(d'\) of the \({\mathsf {AC}}_0\) circuits that the PRF fools. This gives us the following “weak” unconditional natural-proofs barrier.
Theorem 2 (“Weak” Natural-Proofs Barrier (informal, see 5)). Let \(d \geq 5\), and \(\Phi : \mathop{\mathrm{\{0, 1\}}}^{2^n} \mapsto \mathop{\mathrm{\{0, 1\}}}\) be a natural property constructed in polynomial size and constant depth \(d_\Phi\). Then \(\Phi\) cannot show a lower bound of \(2^{n^\varepsilon}\) for depth \(d\) circuits unless \(\varepsilon< (3d_\Phi+7)/(d-3)\), i.e. unless \(d_\Phi\) is sufficiently large as a function of \(d\), or \(\varepsilon\) is sufficiently small.
Our formal version of the above theorem also generalizes it to properties constructed in quasipolynomial size and constant depth. Note that the above rules out a depth-2 poly-size natural property from being able to prove that a depth-\(20\) circuit requires size at least \(2^{n^{14/17}}\) but it does not rule out a depth-\(3\) poly-size natural property from doing the same.5
This construction is nevertheless useful as a warm-up (it appears in 4) and the PRF it constructs is useful for our next result. Our next result removes the dependence between \(d_\Phi\) and \(d\), by analyzing the PRG construction by Trevisan and Xue [11], which is based on an earlier construction by Ajtai and Wigderson [12].
Our main technical contribution is to “localize” the Trevisan–Xue PRG in constant depth.6 In their PRG, the pseudorandom output string is, say, an \(N\)-bit string which is output by a circuit of size comparable to \(N\), when given a seed of length \(\approx \mathsf{polylog}(N)\). Since we need a PRF, we need the \(N\)-bit string which is output to be the truth-table of an \({\mathsf {AC}}_0\) circuit \(C\) of depth \(d\) and size \(2^{n^{O(1/d)}}\). In other words, we must generate a pseudorandom circuit \(C\) and then the \(i\)-th bit of the pseudorandom output string is \(C(i)\). Indeed this can be done, and it yields a pseudo-random function distribution fooling distinguishers of arbitrary constant depth. This gives us our stronger natural-proofs barrier.
Theorem 3 (Natural-Proofs Barrier (informal, see 8)). Let \(d \geq 7\), and \(\Phi : \mathop{\mathrm{\{0, 1\}}}^{2^n} \mapsto \mathop{\mathrm{\{0, 1\}}}\) be a natural property constructed in polynomial size and constant depth \(d_\Phi\). Then \(\Phi\) cannot show a lower bound of \(2^{n^\varepsilon}\) for depth \(d\) circuits, unless \(\varepsilon< 7/(d-5)\).
Again, our formal version of the above theorem generalizes it to properties constructed in quasipolynomial size as well. Note that we can now rule out any constant depth poly-size natural property from being able to prove that a depth-\(20\) circuit require \(2^{n^{7/15}}\) size. In fact, even \(\log \log\)-depth poly-size natural properties cannot prove it. The lower bound of \(2^{n^{8/(d-1)}}\) is unconditionally out of reach for \({\mathsf {AC}}_0\)-natural properties for all \(d>33\).
While we consider this to be a very interesting barrier, the theorem falls short of the ideal parameters in 1 by a constant factor in the exponent. But notice that this constant factor in the exponent is exactly the same regime that follows from the assumption that there exist sufficiently secure \(\mathsf{NC}_1\) PRFs, and here we have proven it unconditionally, even though we only fool \({\mathsf {AC}}_0\) distinguishers.
The proof has a notable self-referential feature. The centerpiece of the PRG of Ajtai–Wigderson is a repeated application of the Switching Lemma. The Trevisan–Xue improvement, which we do need, uses a derandomization of the Switching Lemma. And so we have used the Switching Lemma to show, for example, that the Switching Lemma cannot prove Valiant’s desired lower-bound. We emphasize: the Switching Lemma, which is used to prove lower-bounds against constant-depth-circuits, has here been used to formally show that the Switching Lemma cannot prove better lower-bounds.
This result gives a concrete instance of a broader intuition surrounding the natural-proofs barrier, that it reveals a self-referential obstacle against proving lower-bounds (see [13], [14]). If one informally thinks of natural proofs as a proof system, the natural-proofs barrier could be written as: \[\begin{align} \mathsf{CryptoIsPossible} \implies \mathsf{NaturalProofs} \nvdash \text{``}\mathsf{P}\neq \mathsf{NP}\text{''}. \end{align}\]
Although \(\mathsf{NaturalProofs}\) is not a formal proof system, this slogan captures the sense in which the barrier resembles a self-obstruction phenomenon: Under cryptographic assumptions, natural proofs cannot show that \(\mathsf{P}\neq \mathsf{NP}\), and so in particular they cannot prove those same cryptographic assumptions. Informally, natural proofs fail because the same computational hardness that one hopes to prove can give rise to pseudorandom objects that evade the proof technique.
In the Razborov–Rudich setting this obstruction is conditional on cryptographic assumptions. In our setting, for \({\mathsf {AC}}_0\)-natural proofs against constant-depth circuits, the obstruction is unconditional, and the self-referential aspect is especially visible. The Switching Lemma is the main tool behind the known lower bounds against constant-depth circuits. Yet, through the Ajtai–Wigderson and Trevisan–Xue pseudorandom generators, the Switching Lemma also helps construct the pseudorandom functions that rule out stronger lower bounds by \({\mathsf {AC}}_0\)-natural proofs. Thus the same method that proves the known lower bounds also explains why that family of methods cannot prove stronger lower bounds.
The explanatory power of the natural-proofs barrier applies to different computational models where lower-bound provers are stuck, not just Boolean circuits and formulas. For example, a natural-proofs barrier can be established also in the context of algebraic complexity [15] (although some subtlety is needed in this context and the barrier is less certain [16]) and data-structure lower-bounds in the cell-probe model [17], [18]. We seem to be witnessing a repeated, reliable appearance of the natural-proofs barrier along the entire lower-bounds frontier.
The primary implication of the natural-proofs barrier is that it rules out natural proofs of lower bounds against strong complexity classes that contain sufficiently secure PRFs. Thus, for example, since it is believed that \({\mathsf {TC}}_0\) contains such PRFs, we do not expect that we can prove lower bounds against this class by natural proofs. However, the barrier does not seem to address why even for weaker classes we are stuck. For example, we have failed to prove super-quadratic lower-bounds against branching programs since Nečiporuk in 1966 [19], [20], or super-cubic lower-bounds against Boolean formulas [21]–[27], or super-linear lower-bounds against Boolean circuits (we are stuck at \(5n\) [28], [29]). It is conceivable that there are PRFs precisely at these thresholds. Along these lines, Raz [30] recently showed that \(n\cdot (\log n)^{\omega(1)}\) (“strongly super-linear”) lower-bounds against (Boolean or algebraic) circuits computing linear functions cannot be proven with natural proofs under strong but reasonable cryptographic assumptions. Fan, Li, and Yang [6] considered circuit constructions of PRFs which have oracle access to the function. They used this to show that under suitable assumptions, certain black-box techniques cannot yield strong lower bounds.
For a circuit class \(\mathop{\mathrm{\mathcal{C}}}\) the Minimum Circuits Size Problem with respect to \(\mathop{\mathrm{\mathcal{C}}}\) (\(\mathop{\mathrm{\mathsf{MCSP}}}_{\mathop{\mathrm{\mathcal{C}}}}\)) asks, given the truth table of a function \(f\), whether \(f\) can be computed by a circuit in \(\mathop{\mathrm{\mathcal{C}}}\). When \(\mathop{\mathrm{\mathcal{C}}}\) is the class of general circuits of size \(o(2^n / n)\) we drop it from subscript. \(\mathop{\mathrm{\mathsf{MCSP}}}\) is easily shown to be NP and it is commonly conjectured to be NP-hard. Its NP-hardness is only known in restricted cases [31], [32] or under complexity assumptions [33]. There are also unconditional lower bounds for MCSP against various restricted circuit classes (see, e.g., [34], [35]).
Observe that \(\neg \mathop{\mathrm{\mathsf{MCSP}}}_{\mathop{\mathrm{\mathcal{C}}}}\) is a large and useful property against \(\mathop{\mathrm{\mathcal{C}}}\). Furthermore, any lower bound for \(\mathop{\mathrm{\mathsf{MCSP}}}_{\mathop{\mathrm{\mathcal{C}}}}\) shows the extent of non-constructiveness of this property. Natural-proofs barriers say that every large and useful property must be non-constructive. So the direction that we propose and prove results in also proves lower bounds for \(\neg \mathop{\mathrm{\mathsf{MCSP}}}_{\mathop{\mathrm{\mathcal{C}}}}\).
Specifically for a size parameter \(s = 2^{n^{O(1/d)}}\), consider the class \(\mathop{\mathrm{\mathcal{C}}}\) of depth-\(d\) size-\(s\) \({\mathsf {AC}}_0\) circuits. An implication of our results is that \(\mathop{\mathrm{\mathsf{MCSP}}}_{\mathop{\mathrm{\mathcal{C}}}}\) is not in poly-size \({\mathsf {AC}}_0\). We note the two most closely related results we found in the literature. Cheraghchi et al. [35] study the \({\mathsf {AC}}_0\) constructiveness of \(\mathop{\mathrm{\mathsf{MCSP}}}\) and prove a much stronger lower bound, but this has no direct implication on the \({\mathsf {AC}}_0\) constructiveness of \(\mathop{\mathrm{\mathsf{MCSP}}}_{\mathop{\mathrm{\mathcal{C}}}}\). Ilango [32] studies \(\mathop{\mathrm{\mathsf{MCSP}}}_{\mathop{\mathrm{\mathcal{C}}}}\) where \(\mathop{\mathrm{\mathcal{C}}}\) is \({\mathsf {AC}}_0\) formulae, showing that it is NP-hard under quasipolynomial-time randomized reductions, but says nothing of the circuit variant that our paper focuses on.
The paper by Cheraghchi et al. [35] is also relevant because their result about the \({\mathsf {AC}}_0\) constructiveness of \(\mathop{\mathrm{\mathsf{MCSP}}}\) lower bounds uses localizations of PRGs, but in an entirely different manner. Their idea is to restrict the input truth table of MCSP. With the restriction being easy to compute locally by a small circuit (with no depth restrictions) it follows that there is a small circuit whose truth table agrees with said restriction. However the number of truth tables that agree with the restriction is too large for them all to be easy, so the restriction cannot make MCSP constant. Since such restrictions exist that make any \({\mathsf {AC}}_0\) circuit constant, their lower bound on MCSP follows. Interestingly they use Trevisan–Xue’s derandomization of the switching lemma to generate such restrictions locally.
We start with some basic notation. We denote the set of all Boolean functions in \(n\) variables by \({\mathcal{F}}(n)\), and the set of all Boolean functions in \(n\) variables computable by depth-\(d\) circuits of size \(S\) by \({\mathcal{F}}({n, d, S})\).
Definition 1 (Partial Assignment). A partial assignment on \(N\) bits is represented as \(X \in \{0,1,\ast\}^N\). Indices \(\{u : X_u = \ast\}\) are the free indices of \(X\) and the rest are the fixed indices.
Partial assignments are closely related to restrictions.
Definition 2 (Restriction). A restriction is represented as \(\rho : [N] \to \{0,1,\ast\}\). The free indices of \(\rho\) is the set \(\rho^{-1}(\ast)\) and the rest are the fixed indices. We also represent a restriction as \(I \mapsto \alpha\) where \(I\) is the set of fixed indices of the restriction and \(\alpha \in \{0,1\}^{|I|}\) are the values set in the fixed indices. A restriction can act on various objects:
Composition of two restrictions on \(N\) bits: Applying restrictions \(\rho_0\) and then \(\rho_1\) is equivalent to applying their composed restriction \(\rho_0\rho_1\) where \[\rho_0\rho_1(u) = \begin{cases} \rho_0(u) & \text{if }\rho_0(u) \in \{0,1\}\\ \rho_1(u) & \text{otherwise.} \end{cases}\]
Given a partial assignment \(X \in \{0,1,\ast\}^N\), applying \(\rho\) to \(X\) would produce the partial assignment \(X'\) where \[X'_u = \begin{cases} X_u & \text{if }X_u \in \{0,1\}\\ \rho(u) & \text{otherwise.} \end{cases}\] Note that \(\rho_0\rho_1\) applied to \(X\) is the same as applying \(\rho_0\) to \(X\) and then applying \(\rho_1\) to the result.
For a function \(\Phi : \{0,1\}^N \to \{0,1\}\), restricting with \(\rho := I \mapsto \alpha\) yields the restricted function \(\Phi|_{\rho} : \{0,1\}^{N - |I|} \to \{0,1\}\) defined as \(\Phi|_{\rho}(X) = \Phi(X')\) where \(X'\) is equal to \(\alpha\) in indices \(I\) and equal to \(X\) on the other indices.
The notion of a natural proof is not a formal notion: there is no rigorous definition, and this is for good reason (as we shall see). Instead, the formal notion is that of a natural property.
Definition 3 (\({\mathsf {AC}}_0\)-natural properties). Let \(n,d,S,d_\Phi,S_\Phi \in \mathbb{N}\) and \(p \in (0,1)\). An \((n,d,S,d_\Phi,S_\Phi,p)\)-natural property is a predicate \(\Phi:\{0,1\}^{2^n}\to\{0,1\}\),7 such that:
(Usefulness) If \(f \in {\mathcal{F}}({n,d,S})\), then \(\Phi(f) = 0\). I.e. the property rejects all truth tables of easy functions.
(Largeness) If \(f \in {\mathcal{F}}(n)\) is chosen uniformly at random, then \(\Pr_f[\Phi(f) = 1] \geq p\). I.e., the property is true of a random function with “high” probability \(\ge p\).
(Constructivity) \(\Phi \in {\mathcal{F}}({2^n,d_\Phi,S_\Phi})\). I.e., the property is itself easy.
If we omit \(p\), then we are considering that \(p = \Omega(1)\). In fact we will have \(p\) close to \(1\) for all natural proofs we will consider.
Let us now argue why the definition of a natural proof should actually be an informal definition. Note that if we have an \((n,d,S,d_\Phi,S_\Phi)\)-natural property \(\Phi\) such that \(\Phi(f) = 1\), this necessarily implies that the function \(f\) does not have circuits of depth \(d\) and size \(S\). I.e., \(\Phi(f) = 1\) gives us a lower-bound on the complexity of \(f\), which follows from usefulness. One might then be tempted to define a natural proof as a proof that explicitly constructs a natural property \(\Phi\) and shows that \(\Phi(f) = 1\). However, the reality is that most lower-bounds in the literature explicitly use specific properties of the function \(f\), which are not true of a random function, or properties which appear to be hard to compute efficiently when given the truth-table of \(f\). It would then seem that such lower-bounds are not natural proofs, because the lower-bound-implying property does not obey largeness, or constructivity, hence it is not natural.
The very surprising fact is that, whenever one finds such a seemingly-unnatural proof in the literature, then systematically, time and again, after a bit of thinking, one concludes that the proof can be changed only slightly, to extract from it a similar argument which does not actually require any of the specific properties of \(f\) that were used in the original argument, and which indeed also applies to a random function. And we will find that this extracted property is very simple to compute when given \(f\) as input. One has then obtained a natural property from the original lower-bound proof.
This process of extraction of a natural property is called naturalizing a lower-bound proof. We may then think of it as follows: the proof did not seem natural, but deep down it actually was a natural proof. So in practice we call any naturalizable lower-bound proof a natural proof. Of course, such a concept of natural proof is necessarily imprecise: there is no way to formally specify or even predict what will be necessary to do in order to naturalize a given lower-bound proof. Nonetheless, if a natural-proofs barrier exists, no lower-bound proof can exist which can be naturalized, no matter how one might try to do it. So this imprecise concept is somehow the right concept. We must therefore settle for an informal definition:
Definition 4 (informal). If we have a proof that a function \(f:\{0,1\}^n\to\{0,1\}\) cannot be computed by depth-\(d\), size-\(S\) circuits, and from this proof we can somehow extract an \((n,d,S,d_\Phi,S_\Phi,p)\)-natural property \(\Phi\), where \(p\) is reasonably large (e.g., \(p = \Omega(1)\)), \(d_\Phi\) is a constant and \(S_\Phi\) is not too large (e.g. \(S_\Phi \le |f|^{O(1)} = 2^{O(n)}\), or maybe \(S \le 2^{(\log |f|)^{O(1)}} = 2^{n^{O(1)}}\)), and the proof can be adapted to show that \(\Phi(f) = 1\), then we call this proof an \({\mathsf {AC}}_0\)-natural proof.
Definition 5. An \((n,d,S)\)-function generator is a distribution \(\mu\) over \({\mathcal{F}}(n,d,S)\). In this paper our function generators will additionally be “uniform”. That is, there is a single depth-\(d\) size-\(S\) circuit which has \(n\) input wires and an additional number of seed wires with the distribution \(\mu\) being generated by sampling the values of the seed wires uniformly at random and outputting the function (from \(\{0,1\}^n\) to \(\{0,1\}\)) computed by the remaining circuit.
Definition 6 (\(\epsilon\)-fooling). Let us consider a function generator \(\mu\) and let \(\mathcal{A}\) be a class of algorithms, which we call distinguishers. We say that \(\mu\) \(\epsilon\)-fools \(\mathcal{A}\) iff: \[\forall A \in \mathcal{A}: \left\lvert\Pr_{f\sim\mu }[A(f)] - \Pr_{f\sim \mathsf{Unif}}[A(f)]\right\rvert < \epsilon,\] where \(\mathsf{Unif}\) denotes the uniform distribution.
Definition 7. An \((n,d,S,d_\Phi,S_\Phi,\epsilon)\)-pseudorandom function generator is an \((n,d,S)\)-function generator that \(\epsilon\)-fools all distinguishers in \({\mathcal{F}}(2^n,d_\Phi,S_\Phi)\).
As noted in the introduction, the existence of PRFs in a circuit class precludes the existence of natural proofs against said circuit class. Here we state the instantiation of this logic relevant to our paper.
Lemma 1. Let \(n,d,S,d_{\Phi},S_{\Phi}\in \mathbb{N}\) and \(\epsilon \in (0,1)\). If there is an \((n,d,S,d_\Phi,S_\Phi,\epsilon)\)-pseudorandom function generator, then there is no \((n,d,S,d_\Phi,S_\Phi,\epsilon)\)-natural property.
Proof. We will prove this by contradiction. Let \(\Phi\) be an \((n,d,S,d_\Phi,S_\Phi,p)\)-natural property and let \(f_1,f_2 : \{0,1\}^n \to \{0,1\}\) be functions sampled from the PRF and from the uniform distribution respectively. Since \(f_1 \in {\mathcal{F}}(n,d,S)\), from the usefulness of \(\Phi\) we know \(\Phi(f_1)=0\) with probability \(1\). On the other hand from the largeness of \(\Phi\) we know that with probability at least \(\epsilon\), \(\Phi(f_2)=1\). Hence \(\Phi\) is a distinguisher, and by constructivity it is in \({\mathcal{F}}(2^n,d_{\Phi},S_{\Phi})\). This contradicts the definition of the PRF. ◻
We will use the following folklore proposition about PRFs, whose proof we include in Appendix 8 for completeness.
propositionfooling Let \(\mu_1\) be a distribution on \(N_1\) bit strings that \(\epsilon_1\)-fools a class of algorithms \(\mathcal{A}\) that is closed under restrictions and padding. Similarly define \(\mu_2\) with parameters \(N_2\) and \(\epsilon_2\). Then we have the following observations.
For any \(I \subseteq [N_1]\), the marginal of \(\mu_1\) to the indices \(I\) will also \(\epsilon\)-fool \(\mathcal{A}\).
The distribution \(\mu_1 \times \mu_2\) will also \((\epsilon_1+\epsilon_2)\)-fool \(\mathcal{A}\). (In particular \(\mu_1 \times \mathsf{Unif}_{N_2}\) continues to \(\epsilon_1\)-fool \(\mathcal{A}\).)
We will need the following result, which is a consequence of a result of Ajtai and Ben-Or [36], to show that many known lower bound proofs in fact give \({\mathsf {AC}}_0\)-natural properties. We provide a proof of it in Appendix 8.
theoremapproxcount There exists a function \(\mathsf{GapCount}^{\times}_{n,t,\varepsilon} : \{0,1\}^n \to \{0,1\}\) satisfying \[\mathsf{GapCount}^{\times}_{n,t,\varepsilon}(x) = \begin{cases} 0 & \text{if } |x| \le t,\\ 1 & \text{if } |x| \ge \left(1 + \varepsilon\right) \cdot t \end{cases}\] that is computable by a circuit of depth \(O(1+\log (1/\varepsilon)/\log \log n)\) and size polynomial in \(n\).
In this section we show that almost all known lower-bound techniques against constant-depth \({\mathsf {AC}}\)-circuits are \({\mathsf {AC}}_0\)-natural. We will cover lower-bounds based on the Switching Lemma (3.1.1), lower-bounds bounds based on sensitivity and concentration of the Fourier spectrum (3.1.2), and top-down lower-bounds ([sec:HJP,sec:PPZ,sec:GRSS]). Among these some of the top-down lower-bounds are not \({\mathsf {AC}}_0\)-natural, but for all except a couple of them we were able to find thematically similar \({\mathsf {AC}}_0\)-natural proofs proving nearly the same lower bounds. It could be that they do, in fact, naturalize, and we simply did not figure out how to do it: we leave naturalizing these proofs as an open problem.
These techniques generally analyze circuits in a bottom-up fashion, that is by starting from the input level and working the way up to the output gate.
The first lower-bounds against \({\mathsf {AC}}_0\) circuits were proven by Ajtai [37] and Furst-Saxe-Sipser [38], who showed that a function \(f\) which is computed by a small CNF, becomes expressible by a small DNF with high probability over a random subcube \(\rho\) of reasonably large dimension, so the order of the AND/OR can be switched. It follows from this Switching Lemma that any function \(f\) computable by a small depth \(d\) circuit can also be computed by a depth \(d-1\) circuit inside the subcube. The parameters for this lemma were later improved by Yao [39], and ultimately Håstad [40]. From Håstad’s Switching Lemma we can derive the following corollary:
Corollary 1. If \(f \in {\mathcal{F}}({n,d,S})\), and \(\rho\) is a \(p\)-random restriction with \(p = \frac{1}{O(\log S)^{d-2}}\), then \[\Pr[f|_\rho\text{ can be computed by a k-CNF}] \ge 1 - o(1),\] where \(k= 2 \log S\). In particular, \(f\) has a monochromatic subcube of dimension \(\Omega(p \cdot n) - k\). If \(S< 2^{\Omega\left(n^{\frac{1}{d-1}}\right)}\), this dimension is at least \(2 \log n\).
From this Corollary it follows that any function \(f\), such as parity, which is non-constant on every Boolean subcube of dimension \(2\log n\) is not in \({\mathcal{F}}({n,d,S})\). Given the truth table of \(f\), i.e., given \(f \in \{0,1\}^N\), where \(N=2^n\), we can test whether \(f\) is non-constant in every subcube of dimension \(s\) by an \({\mathsf {AC}}_0\) circuit of depth \(d_\Phi = 2\) and size \(S_\Phi =O(N^2)\). A random function will have this property with probability \(1 - o(1)\). And so we have a \((d,S,d_\Phi,S_\Phi,o(1))\)-natural proof.
That this proof is \({\mathsf {AC}}_0\)-natural had already been observed by Razborov and Rudich. In the time since, many variants of the Switching Lemma have been proven [41]–[46] For example, in [43], Rossman has shown that the function \(\mathsf{CLIQUE}_k:\{0,1\}^{\binom{n}{2}} \to \{0,1\}\), which indicates whether a given undirected graph has a clique of (constant) size \(k\), cannot be computed by constant-depth circuits of size \(O(n^{\frac{k}{4}})\). The core technical lemma is the following:
Theorem 4. Suppose \(f_n \in {\mathcal{F}}({\binom{n}{2},O(1), O(n^t)})\), i.e. \(f_n\) is a function on \(\binom{n}{2}\) bits, computed by depth \(d = O(1)\) circuits of size \(O(n^t)\), and \(t > 1/2\). For any integer \(k \ge 3\) and \(\alpha = \frac{1}{2t-1}\), let \(G = \mathsf{ER}(n, n^{-\alpha})\) be an Erdös-Rényi random graph, and let \(A\) be a uniform random set of \(k\) vertices of \(G\). Then, for all sufficiently large \(n\), \(f_n(G) = f_n(G \cup K_A)\) with high probability over the choice of \(G\) and \(A\), where \(K_A\) is the clique on \(A\).
If \(t \le \frac{k}{4}\), for the given choice of \(\alpha\), we have that \(\Pr[\mathsf{CLIQUE}_k(G) = 1] = o(1)\), and of course \(\mathsf{CLIQUE}_k(G \cup K_A) = 1\) always, so \(f_n\) does not compute \(\mathsf{CLIQUE}_k\). More generally, \(f_n\) will fail to compute any function \(f\) such that \(\Pr_{G,A}[f(G) = f(G \cup K_A)]\) is not close to \(1\). We can then take the following as our natural property. \(\Phi(f) = 1\) if and only if, for every graph \(G\) without a \(k\)-clique, \(\Pr_A[f(G) \neq f(G \cup K_A)] \ge \frac{1}{4}\). If \(f\) is a random function, we expect about half of the choices \(A\) to give \(f(G) = f(G \cup K_A)\), and since there are at least \(\binom{n}{3} \gg \binom{n}{2}\) such choices, by concentration of measure it is \(\ll 2^{-\binom{n}{2}}\)-likely that some graph \(G\) will have \(f(G) \neq f(G \cup K_A)\) for fewer than a \(\frac{1}{4}\) fraction of the choices of \(A\). We take a union bound and conclude that this property is large. We can check whether this property holds using a constant depth circuit of size \(2^{O(\binom{n}{2})}\), by taking an AND over all \(G\), and counting the number of \(A\) such that \(f(G) \neq f(G \cup K_A)\) (this is a small number, we can count it precisely). Then this property, and hence Rossman’s proof, are \({\mathsf {AC}}_0\)-natural.
The average sensitivity of a function \(f:\{0,1\}^n\to\{0,1\}\) is the expected number of sensitive coordinates: \(S(f) = \frac{1}{2^n} \sum_{x\in\{0,1\}^n} S(f,x)\), where \(S(f,x) = \lvert\{i \in [n] \mid f(x) \neq f(x \oplus e_i) \}\rvert \in \{0, \ldots, n\}\). In [47], Boppana has proven:
Theorem 5. If \(f \in {\mathcal{F}}({n,d,S})\), then \(S(f) = O(\log S)^{d-1}\).
Since the sensitivity of parity is \(n\), we get the same lower-bound of \(S \ge 2^{\Omega(n^{\frac{1}{d-1}})}\) against parity. Using approximate counting ([thm:approximate-counting]), a circuit of constant depth and size \(2^{O(n)}\) can compute \(\sum_{x \in \{0,1\}^n} S(f,x)\) up to an additive error of \(\frac{2^n}{n^2}\). This is enough to estimate \(S(f)\) up to a \(o(1)\) additive error, and so any lower-bound proven from 5 is \({\mathsf {AC}}_0\)-natural.
A number of results starting with Linial, Mansour, and Nisan [48] show that constant-depth circuits can be well-approximated (in \(\ell_2\)-norm) by low-degree polynomials [44], [45], [49]. The strongest such result is by Tal [50]:
Theorem 6 ([50]). If \(f \in {\mathcal{F}}({n,d,S})\), then \[W^{\ge k}(f) =\sum_{T: |T| \ge k} \hat{f}(T)^2 \le 2 \cdot 2^{-k/O(\log S)^{d-1}},\] where \(\hat{f}(T) = \frac{1}{2^n}\sum_{x \in \{0,1\}^n} (-1)^{f(x)} \cdot (-1)^{|x \cap T|}\) is the Fourier coefficient of \(f\).
By choosing \(k = O(\log S)^{d-1}\) sufficiently large, we conclude that the entire Fourier tail has mass less than, say, \(\frac{1}{10}\). But parity has all its Fourier mass at level \(k = n\), and so we get the same lower-bound of \(S \ge 2^{\Omega(n^{\frac{1}{d-1}})}\) against parity.
Again, while we cannot compute the Fourier tail \(W^{\ge k}(f)\) exactly, we can use approximate counting to approximate the mass of the Fourier tail. Indeed, \[W^{\ge k}(f) = \frac{1}{2^{2n}}\sum_{T:|T| \ge k} \sum_{x,y\in\{0,1\}^n} (-1)^{f(x)} \cdot (-1)^{f(y)} \cdot (-1)^{|x\Delta y|}.\] We can construct a constant-depth circuit of size \(2^{O(n)}\) which computes every term in the sum, and using multiplicative approximate counting we can estimate the sum of the positive and negative terms up to a multiplicative error of \(1 \pm \frac{1}{n^r}\), subtract the two estimates and divide by \(2^{2n}\) (which is an easy division, even for \({\mathsf {AC}}_0\)), to get an estimate of \(W^{\ge k}(f)\) up to a multiplicative error of \(O(1 \pm n^{-r})\). (Observe that here an additive approximation is not enough.) This is enough precision to distinguish the case when \(f\) is computed by a simple constant-depth circuit, who will have Fourier tail \(\le \frac{1}{10}\) versus a random function whose Fourier spectrum is roughly uniformly distributed, hence will have Fourier tail \(\ge 1 - o(1)\).
Such techniques generally analyze circuits in a top-down fashion, that is by starting from the output gate, working the way down to input gates until reaching a contradiction.
Here we primarily focus on the the depth-\(3\) lower bound technique of Håstad, Jukna and Pudlák [2]. We will note that their property is not a natural property because it is small, and we will mention an \({\mathsf {AC}}_0\)-natural property that is similar both in principle and in getting nearly the same lower bounds. We go into more detail about these properties in Appendix [sec:topdownproperties].
Håstad et al.’s lower bound technique works as follows. From a small \(\Sigma_3\) circuit \(C\) (i.e., depth 3 with a top \(\mathsf{OR}\) gate) that computes \(f\) one can easily find a CNF \(D\) that rejects every input in \(f^{-1}(0)\) and accepts every input in a large subset \(T \subseteq f^{-1}(1)\). Now consider an input \(y\) such that for every \(Q \subseteq [n]\) of size at most \(k\), there is an \(x \in T\) such that \(x_Q = y_Q\). Such a \(y\) is called a \(k\)-limit of the set \(T\). If \(D\) has bottom fan-in \(k\) then from the perspective of each clause in \(D\), \(y\) looks exactly like an element \(x \in T\), so \(y\) will also be accepted by all the clauses and hence by \(D\). Hence such a \(k\)-limit of \(T\) cannot exist in \(f^{-1}(0)\).
The actual task is then to come up with what we will call “limitful” functions, i.e. functions \(f\) such that in every partition of \(f^{-1}(1)\) into at most \(\ell\) parts, at least one part has a \(k\)-limit in \(f^{-1}(0)\). Such functions would require \(\Sigma^k_3\) circuits (\(\Sigma_3\) with bottom fan-in \(k\)) of size at least \(\ell\). The property of being limitful is far from constructive, although it is large and useful.
Håstad et al. use Ramsey theoretic arguments similar to those used in the sunflower lemma to show that if \(f\) is a threshold function it is limitful. The property they use of \(f\) is small (and hence not natural), and this seems to be needed for the Ramsey theoretic arguments to work. With this they show that the Threshold\(_{n,n/k}\) function (that answers “Does the \(n\)-bit input have at least \(n/k\) ones?”) requires \(e^{(n/k) \cdot (1-o(1))}\) size \(\Sigma_3^k\) circuits. A lower bound of \(e^{(n/2k) \cdot (1-o(1))}\) also follows for Majority since it embeds the above functions on \(n/2\) bits.
(For the \(k=3\) case specifically, a better lower bound of \(\approx e^{1.35 n/2k}\) for Majority is known [3]. This property is even smaller and the analysis does not even involve \(k\)-limits. This is detailed later on in this section.)
For \(\Sigma_3\) lower bounds they use an initial restriction to the input that makes the bottom fan-in bounded. The restriction turns a threshold function into a new threshold function, and so the \(\Sigma^k_3\) lower bounds can be used. With this they get a lower bound of \(\approx 2^{0.849\sqrt{n}}\). The property that \(f\) needs for this restriction to also be a part of the lower bound proof would be even smaller, although it would still be computable and useful.
Meir and Wigderson [51] came up with a different way of finding \(k\)-limits. They showed that for any set \(X\) of size at least \(2^{n-o(n/k)}\), almost all its neighbours are \(k\)-limits. That is, if we choose \(x \in X\) and \(i \in [n]\) uniformly at random, then \(x \oplus e_i\) is a \(k\)-limit of \(X\) with probability at least \(1-o(1)\). This provides a new way to generate limitful functions. Let \(f\) be any function with a large number of \(x \in f^{-1}(1)\) having high sensitivity. This yields an \({\mathsf {AC}}_0\)-natural property that proves lower bounds against \(\Sigma^k_3\) circuits. The large number of \(k\)-limits that it guarantees allows us to also use this property as is to prove \(\Sigma_3\) lower bounds (see Appendix [sec:topdownproperties] for details). This \({\mathsf {AC}}_0\)-natural proof gives a \(\Sigma^k_3\) lower bound of \(2^{(1-o(1))n/2(k+1)}\), and a \(\Sigma_3\) lower bound of \(2^{(1-o(1))\sqrt{n}/2}\).
Håstad et al. [2] also show a \(\Sigma_3\) lower bound of \(2^{\Omega(\sqrt{n})}\) on the function \(\mathrm{AND}_{\sqrt{n}} \circ \mathrm{OR}_{\sqrt{n}} \circ \mathrm{AND}_2\). They prove this via the same technique covered above, showing that it is limitful. However in this setting the natural property used by Meir and Wigderson does not apply and hence this separation of \(\Sigma_3\) vs \(\Pi_3\) complexity does not have a natural proof yet. We leave it as an open problem to find an \({\mathsf {AC}}_0\)-natural lower bound of \(2^{\Omega(\sqrt{n})}\) for the above function.
Paturi, Pudlák and Zane [52] proved a combinatorial lemma regarding \(k\)-CNFs which they used to devise a non-trivial algorithm for satisfiability of \(k\)-CNFs, and to show a tight \(\Omega(n^\frac{1}{4} 2^{\sqrt n})\) lower-bound on the size of depth-3 circuits that compute Parity. The main component of their result is the following lemma. For a set \(S \subseteq \mathop{\mathrm{\{0, 1\}}}^n\) we say that \(x \in S\) is \(j\)-isolated if there are at least \(j\) coordinates such that flipping \(x\) in any one of those coordinates results in an assignment outside \(S\).
Lemma 2 (Satisfiability Coding Lemma [52]). Let \(F\) be an \(n\)-variate \(k\)-CNF. For every \(j \in [n]\), the number of \(j\)-isolated satisfying assignments of \(F\) is at most \(2^{n - j/k}\).
A \(\Sigma^k_3\) circuit is a \(\Sigma_3\) circuit such that every gate in the bottom layer has fan-in at most \(k\). Since a \(\Sigma^k_3\) circuit, in particular, gives a covering of \(j\)-isolated accepting inputs of a function, the following general lower bound is an immediate corollary.
Corollary 2. Let \(f\) be an \(n\)-variate function which accepts \(S\) \(j\)-isolated assignments. Then any \(\Sigma^k_3\) computing \(f\) has size at least \(S/2^{n - j/k}\). In particular,
any \(\Sigma^k_3\) circuit computing Parity has size at least \(2^{\frac{n}{k} - 1}\) [52],
a function \(f\) sampled uniformly at random requires \(\Sigma^k_3\) circuits of size \(2^{\frac{n}{2k} - o(n)}\).
The latter follows by observing that a random function has \(2^{n - o(n)}\) \((\frac{n}{2} - o(n))\)-isolated accepting inputs with high probability. Using the approximate counting circuit of [thm:approximate-counting], we obtain an \({\mathsf {AC}}_0\)-natural property useful against \(\Sigma^k_3\) circuits of size \(2^{n/2k - o(n)}\). Therefore, the weaker PPZ lower bound is an \({\mathsf {AC}}_0\)-natural proof.
Paturi, Saks, and Zane [53] showed a near-maximal lower bound for \(\Sigma^2_3\) circuits computing affine dispersers. An affine disperser for dimension \(d\) is a function that is not constant under any affine space of dimension \(d\). They showed that any \(\Sigma^2_3\) circuit that computes an affine disperser for dimension \(o(n)\) has size at least \(2^{n - o(n)}\). No such lower bound is known for \(\Sigma^k_3\) where \(k \ge 3\). It is easy to see that a random function is affine disperser for dimension \(O(\log n)\). Furthermore, the property of being an affine disperser for dimension \(d\) can be trivially checked by a depth-3 circuit of quasipolynomial size for \(d = O(\log n)\): exhaustively go through all affine spaces of dimension \(d\) and check whether the function is constant in that affine space. It follows that the lower bound of [53] is a quasipolynomial-\({\mathsf {AC}}_0\)-natural proof.
Paturi, Pudlák, Saks and Zane [54] strengthened the Satisfiability Coding Lemma as follows to derive improved \(k\)-SAT algorithms as well as depth-3 circuit lower bounds.
Lemma 3. Let \(F\) be an \(n\)-variate \(k\)-CNF. Then the number of satisfying assignments of \(F\) which are of Hamming distance at least \(\Delta\) from any other satisfying assignment is at most \(2^{(1 - \frac{\pi^2}{6k} + O(\frac{1}{\Delta k}))n}\).
Corollary 3. If \(f\) is the characteristic function of an error correcting code of distance \(\omega(1)\) accepting at least \(S\) inputs, then it requires \(\Sigma^k_3\) circuits of size at least \(S/2^{(\pi^2/6k - o(1))n}\).
To see why this is a natural proof requires some subtlety. Clearly a random function will not be an error correcting code, not even of distance \(2\), since the \(2\)-Hamming ball already has \(n^2\) points, and so no accepting input is isolated. But if we choose a sparse random function, namely, every output \(F(x)\) is chosen independently at random with bias \(\Pr[F(x)=1] = n^{-\omega(1)}\), then with high probability \(F^{-1}(1)\) is an error-correcting code with distance \(\omega(1)\), which accepts \(2^{n-o(n)}\) inputs. Therefore the PPSZ proof is natural, in the sense that it produces a distinguisher which rejects all easy functions (with small \(\Sigma^k_3\) complexity) from sparse random functions chosen with this bias. Moreover, as argued below, this notion of natural is just as relevant to the \({\mathsf {AC}}_0\)-natural-proofs barrier.
We can easily convert an \({\mathsf {AC}}_0\) PRF for unbiased functions into a PRF \(F:\{0,1\}^n\to\{0,1\}\) with any bias which is an inverse power of two. For example, if we want \(\Pr[F(x)=1] = 2^{-q}\), we start by taking a PRF for a slightly larger bitlength \(F':\{0,1\}^{n + \lceil \log q \rceil} \to \{0,1\}\). We then use an AND to get \(F\): \(F(x) = \bigwedge_{x' \in [q]} F'(x x')\). It now follows that \(F\) is sampled among random functions with bias \(2^{-q}\), as promised. An \({\mathsf {AC}}_0\) distinguisher to break \(F\) can be converted to an \({\mathsf {AC}}_0\) distinguisher to break \(F'\) by composing it with the AND circuits that turn \(F'\) into \(F\) (i.e. convert the input function to a biased function as above and then use the distinguisher for \(F\)). This increases the depth of the distinguisher by at most \(1\) and the size by at most \(q\). Therefore, any (unbiased) \({\mathsf {AC}}_0\)-natural-proofs barrier also gives us a barrier for biased \(F\).
The Majority function is a natural candidate for an explicit function that requires depth-3 circuits of size \(2^{\omega(\sqrt{n})}\), i.e., beyond the current barrier [2]. Gurumukhani et al. [3] recently proposed to investigate \(\Sigma^k_3\) complexity of majority as an approach to determine its unrestricted depth-3 complexity. As the first non-trivial case they considered \(k = 3\) and proved new lower bounds on the size of \(\Sigma^3_3\) circuit computing the majority function. Their main result is the following combinatorial lemma.
Lemma 4. Let \(F\) be an \(n\)-variate 3-CNF which rejects every assignment of Hamming less than \(\lfloor n/2 \rfloor\). Then the number of satisfying assignments of \(F\) of Hamming weight exactly \(\lfloor n/2 \rfloor\) is at most \(1.598^n\).
The following lower bound is immediate.
Corollary 4. Let \(f\) be any \(n\)-variate function that rejects all inputs of Hamming weight less than \(\lfloor n/2 \rfloor\) and accepts at least \(S\) assignments of Hamming weight \(\lfloor n/2 \rfloor\). Then any \(\Sigma^3_3\) circuit computing \(f\) has size at least \(S / 1.598^n\).
There are two main issues that make it difficult to render the technique of [3] as natural. Firstly, the property given in 4 is not large; in fact with high probability a random function does not satisfy this property. Secondly, we can indeed artificially condition on rejecting small Hamming weight inputs when sampling a random function. Under this condition we would only need to approximately count the number of accepting inputs in the middle slice which can be done in \({\mathsf {AC}}_0\). Therefore, in this artificial sense, the proof is natural. However, unlike in the case of sampling a sparse random function, as we did in the previous two sections, it is not clear how to construct PRFs supported in \({\mathsf {AC}}_0\) for this distribution, without computing the majority function along the way.
Göös, Riazanov, Sofronova, and Sokolov [55] proved a top-down lower-bound for depth-4 circuits computing Parity. The extra layer is treated using the spreadness lemma [56], and after this the argument is a non-trivial variant of Håstad, Jukna and Pudlák’s depth-3 lower-bound. At a crucial juncture in the proof of Claim 4 (Lemma 4, page 7 of ArXiv version v2), they use the property that every input \(x\) has sensitivity \(S(f,x) = n\). This is the only time they use the fact that \(f\) is parity, but of course, this property is the defining property of the parity function (or its negation). The GRSS proof shows that parity has neither \(\Sigma_4\) nor \(\Pi_4\) circuits. To begin, let us naturalize this proof to show that a random function from a biased distribution does not have \(\Sigma_4\) circuits. By naturalizing this proof we will extract a distinguisher which distinguishes all easy functions from a random function of the appropriate bias. In the same way that we argued earlier, \({\mathsf {AC}}_0\)-computable PRFs \(F\) with bias \(\Pr[f(x) = 1]=1-2^{-q}\) can be constructed from any unbiased PRF \(F'\), by adding only one extra layer of OR gates on top. So the \({\mathsf {AC}}_0\)-natural-proofs barrier also applies to biased functions.
Let \(f\) denote a random function, where each output \(f(x)\) is chosen independently with bias \(\Pr[f(x) = 1] = 1 - \frac{1}{n^{1-\delta}}\) where \(\delta=0.1\). Then, with high probability over the choice of \(f\), it will happen for every \(x \in f^{-1}(0)\), that the \(2\)-wise sensitivity is high: \[\forall x \in f^{-1}(0) \qquad\qquad S_2(f,x) = \frac{|\{ z\in\binom{[n]}{2} \mid f(x \oplus z)\neq f(x)\}|}{\binom{n}{2}} \ge 1 - \frac{2}{n^{1-\delta}}.\] To see this, note for any fixed \(x\) the expected number \(Z\) of \(2\)-neighbours \(x'\) with \(f(x') = 0\) is precisely \(\mu =\frac{1}{n^{1-\delta}} \binom{n}{2}\gg 6n\), and by a Chernoff bound, \[\Pr\left[S_2(f,x) < 1 - 2 \frac{1}{n^{1-\delta}}\right] = \Pr[Z > 2 \mu] \le \exp\left(-\frac{1}{3} \mu\right) = o( 2^{-2n} )\] and hence w.h.p. there will be no such \(x \in f^{-1}(0)\). This means that, for every \(x \in f^{-1}(0)\), there are fewer than \(\frac{2}{n^{1-\delta}} \binom{n}{2}\) strings in \(f^{-1}(0)\) at Hamming distance \(2\) from \(x\). Our natural property will be a small variation of this. We actually want the sensitivity to be high even if I have chosen some set \(I\) of size \(\le \frac{n}{10}\) (say), and am only considering \(2\)-neighbors which do not change any coordinate in \(I\). Our \({\mathsf {AC}}_0\) natural property is then precisely the following: \[\forall x \in f^{-1}(0) \forall I \in \binom{[n]}{\le \frac{n}{10}} \qquad \qquad S_{2,I}(f,x) = \frac{|\{ z\in\binom{[n]\setminus I}{2} \mid f(x \oplus z)\neq f(x)\}|}{\binom{n-|I|}{2}} \ge 1 - \frac{2}{n^{1-\delta}}\] while \(f\) also satisfies \(|f^{-1}(0)| \geq 2^{n-o(n)}\). The same proof as above shows that it is large among random functions chosen with the bias \(1 - \frac{1}{n^{1 - \delta}}\). It is in \({\mathsf {AC}}_0\) by just doing a large AND over all \(x\) and \(I\) and checking the sensitivity requirement, and doing an approximate counting of the \(0\)s in the truth table.
Now let us turn our attention to the GRSS proof. We assume familiarity with the proof and only detail what changes need to be made to the proof in order for it to work for any function with the above property. The sensitivity of parity is used only once, crucially, in the proof of Claim 4. At this point in the proof we found a maximal set \(I\) violating the spreadness condition. If the indicator \(x''\) of \(I\) is in \(f^{-1}(1)\), then the proof is done. Otherwise, the proof takes \(i_0 \in [n]\setminus I\) having the highest probability of being \(1\) among the elements of \(B' = \{x \in A : x_I = 1_I\} - x''\). One argues that this probability is at least \(\frac{m-I}{n-I}\), by noticing that \(|\{(z,i_0) \mid z \in B', z_{i_0}=1\}| = |B'| (m - |I|)\), hence by the pigeonhole principle some \(i_0 \in [n]\setminus I\) must appear in at least \(\frac{1}{n-|I|}\) such pairs, and hence the probability that \(z \in B'\) has \(z_{i_0} = 1\) is at least \(\frac{m-|I|}{n-|I|}\).
To naturalize this part of the argument, we need something slightly stronger, we need to show that there are many choices \(\{i_0, i_1\}\) of two coordinates that have reasonably high probability of being both set to \(1\). Indeed, we can proceed greedily. Repeating the same argument we just did, now with a set of triples, we have \(|\{(z,i_0,i_1) \mid z \in B', z_{i_0 i_1}=1^2\}| = |B'| \binom{m - |I|}{2}\), and hence there exists some choice \(\{i^{(1)}_0, i^{(1)}_1 \}\) with \(\Pr_{z \in B'}[z_{i^{(1)}_0 i^{(1)}_1} = 1^2] \ge \frac{\binom{m-|I|}{2}}{\binom{n-|I|}{2}}\). Now recall that \(B'\) is \((1/p)^{(1-\varepsilon)}\)-spread, and hence \(\Pr_{z \in B'}[z_{i^{(1)}_0 i^{(1)}_1} = 1^2] \le p^{2}\). So we have only removed \(p^{2}\) mass out of our set of triples. This can be done \(\frac{2}{p^{2}} \gg n^{1+\delta}\) times before half the mass has been removed. We then conclude that there are \(\gg n^{1+\delta}\) “high-probability pairs” \(\{i_0,i_1\}\) such that \(\Pr_{z \in B'}[z_{i_0 i_1} = 1^2] \ge \frac{\binom{m-|I|}{2}}{2\binom{n-|I|}{2}}\). Since \(x''\) has \(2\)-sensitivity \(\ge 1 - \frac{2}{n^{1-\delta}}\), the number of distance-2 neighbors \(x'\) of \(x''\) with \(f(x') = 1\) is at least \((1-\frac{2}{n^{1-\delta}})\binom{n}{2} = \binom{n}{2} - O(n^{1+\delta})\). It follows that one of these distance-2 neighbors is equal to \(x'' \oplus 1_{i_0 i_1}\) for one of our “high-probability” pairs. We then set \(I' = I \cup \{i_0, i_1\}\), and then the calculation proceeds as in the proof of Claim 4. The detailed changes needed are: (1) we only get \((1/p)^{1 - 3.1\varepsilon}\)-spreadness for \(B\), so \(2.1\) gets replaced with \(3.1\); (2) the probability \(\Pr_{x\sim A}[x_{I'}=1_{I'} \mid x_I = 1_I]\) is now at least \(\frac{\binom{m-|I|}{2}}{2\binom{n-|I|}{2}} \ge p^2 \frac{1}{4}\); (3) so now, analogous to their proof, the \(p^{-2\varepsilon|J|}\) factor defeats the \(p^{2\varepsilon}\), and the \(p^{-0.1\varepsilon}\) factor defeats the \(\frac{1}{4}\).
We have then concluded that the GRSS proof is natural in the above sense (where largeness is with respect to biased functions), and that any barrier established for unbiased functions will also give us a barrier here. To finish, let us just remark that our proof shows that our biased function does not have \(\Sigma_4\) circuits, but the original proof shows a simultaneous lower-bound for \(\Sigma_4\) and \(\Pi_4\). To correct for this, we can change our property so that we require large sensitivity with respect to \(0\) among inputs whose first bit is \(0\), and large sensitivity with respect to \(1\) for inputs whose first bit is \(1\). A peculiar feature of our depth-4 \({\mathsf {AC}}_0\)-natural lower bound, which was not the case for the other naturalized variants we saw earlier, is that it does not show a lower bound for the originally studied function (in this case Parity).
Braverman’s celebrated result states that polylogarithmic independent distributions fool \({\mathsf {AC}}_0\) circuits [10]. Here, we consider an improvement of it due to Tal [50].
Theorem 7 (Tal [50]). Every \(k\)-wise independent distribution over \(\{0,1\}^n\) with \(k \geq O(\log (S_\Phi/\epsilon))^{3d_\Phi+3}\), \(\epsilon\)-fools every distinguisher \(\Phi: \{0,1\}^n \rightarrow\{0,1\}\) computed by size \(\le S_\Phi\) circuits of depth \(\le d_\Phi\).
In the case of \(d_\Phi=2\), \(k \geq O(\log S_\Phi \log (S_\Phi/\epsilon))\) suffices.
We will use polynomials over finite fields to generate such \(k\)-wise independent distributions locally.
theoremaltevalPoly Let \(n, k, c_1, c_2 \in \mathbb{N}\). There exists a circuit of depth \(c_1+c_2+2\) and size \(2^{\tilde{O}(kn^2)^{1/c_1}+n^{2/c_2}}\) that on input \((\bar{a},y) \in (\{0,1\}^n)^k \times \{0,1\}^n\) outputs \(p(y) \in \{0,1\}^n\) where \(p = \sum_{i=0}^{k-1} a_i z^i \in \mathbb{F}_{2^n}[z]\) and \(y \in \mathbb{F}_{2^n}\).
All the output gates of the constructed circuit are \(\mathsf{AND}\) gates.
The circuit construction uses ideas from [57] to implement multiplication in \(\mathbb{F}_{2^n}\). Their construction was assuming polynomial size and unbounded arity parity gates. We modify their construction for subexponential size with no parity gates. The proof can be found in Appendix 8.
The above gives us a natural approach to create a PRF, using the fact that the outputs of a degree \(k-1\) polynomial chosen uniformly at random exhibit \(k\)-wise independence. For \(x \in \mathbb{F}_{2^n}\) let \(\mathrm{LSB}(x)\) be the least significant bit of the \(n\)-bit representation of \(x\).
Definition 8 (Distribution \(\mu_{n,k}\)). For \(n \in \mathbb{N}\) and \(k \leq 2^{n}\) define the distribution \(\mu_{n,k}\) generated by the following process: Sample uniformly at random \(\bar{a} \in \mathbb{F}^k_{2^{n}}\) and consider the polynomial \(p(x)=\sum_{i=0}^{k-1} a_i x^i\). Output the truth table of \(f(x)=\mathrm{LSB}(p(x))\).
Claim 8. The distribution \(\mu_{n,k}\) defined above is a \(k\)-wise independent distribution over \(\{0,1\}^{2^{n}}\).
Proof. Let \(F = \{c_1,\dots,c_k\} \subseteq \mathbb{F}_{2^{n}}\) be of size exactly \(k\). The linear map from coefficients to evaluations in \(F\), \((a_1,\dots,a_k) \mapsto (p(c_1), \dots, p(c_k) )\), is a bijection because the map can be inverted uniquely via polynomial interpolation. Since the coefficients of the polynomial, \((a_1,\dots,a_k)\), are uniformly distributed over \(\mathbb{F}^k_{2^{n}}\), we must have that \((p(c_1), \dots, p(c_k))\) are uniformly distributed over \(\mathbb{F}^k_{2^{n}}\). And their representations as \(kn\) bit strings is hence also uniformly distributed. Since their least significant bits are a marginal, they are also uniform. Hence every \(k\)-sized marginal of \(\mu_{n,k}\) is uniformly distributed over \(\{0,1\}^k\). ◻
Claim 9. For any \(c_1,c_2 \in \mathbb{N}\) the distribution \(\mu_{n,k}\), defined as above, is an \((n, d, S)\)-function generator with \(d=c_1+c_2+2\) and \(S=2^{\tilde{O}(kn^2)^{1/c_1}+n^{2/c_2}}\).
Proof. For any \(n,k\) the distribution \(\mu_{n,k}\) is supported on the truth tables of circuits that take an input in \(\mathbb{F}_{2^{n}}\), evaluate a degree \(k-1\) polynomial on that input, and extract the last bit. The claim directly follows from [evalPoly]. ◻
We can now put it all together and get our constant-depth PRF.
Theorem 10. For any \(c_1,c_2 \in \mathbb{N}\) there exists \(d=c_1+c_2+2\), \(S=2^{\tilde{O}(\log(S_\Phi/\epsilon)^{3d_\Phi+3}n^2)^{1/c_1}+n^{2/c_2}}\) such that the distribution \(\mu_{n,k}\), for an appropriate \(k\), is a \((n,d,S,d_\Phi,S_\Phi,\epsilon)-\)pseudorandom function generator.
When \(d_{\Phi}=2\), the bound on \(S\) improves to \(2^{\tilde{O}(\log(S_\Phi)\log(S_\Phi/\epsilon)n^2)^{1/c_1}+n^{2/c_2}}\).
Proof. By 8 we know that \(\mu_{n,k}\) is \(k-\)wise independent. 7 gives us bounds on \(k\) such that the PRF \(\mu_{n,k}\) \(\epsilon\)-fools every distinguisher computed by size \(\le S_\Phi\) circuits of depth \(\le d_\Phi\). Substituting this value of \(k\) in 9 gives a circuit of the required size and depth computing \(\mu_{n,k}\). ◻
1 directly tells us that for any \(c \in \mathbb{N}\) there is no \((n,d,S,d_\Phi,S_\Phi,\epsilon)-\)natural proof where \(d,S\) are as above. We now see what parameters \(d_\Phi,S_\Phi\) are needed to get a \(2^{n^\varepsilon}\) lower bound for depth \(d\) circuits.
Corollary 5. Let \(d \in \mathbb{N},d\geq 5\) and \(\varepsilon\geq 2/(d-4)\) be a fixed constant. Let \(\Phi = \{\Phi_n : \mathop{\mathrm{\{0, 1\}}}^{2^n} \rightarrow \mathop{\mathrm{\{0, 1\}}}\}\) be a family of \((n, d, 2^{n^\varepsilon}, d_{\Phi}, S_{\Phi}, 1/2)\)-natural properties. If \(S_\Phi \leq 2^{n^\alpha}\), then \(\varepsilon\leq (3\alpha(d_\Phi+1)+4)/(d-3)\).
Proof. Set \(c_2 = \lceil2/\varepsilon\rceil \leq 2/\varepsilon+1\). Now \(c_1 = d-c_2-2\geq d-2/\varepsilon-3\). We know such a choice is possible because \(\varepsilon\geq 2/(d-4)\).
If \(S_\Phi \leq 2^{n^\alpha}\), then the maximum lower bound provable is at most \(2^{\tilde{O}(n^{(\alpha(3d_\Phi+3)+2)/c_1})+n^{2/c_2}}\). For \(2^{n^\varepsilon}\) to be at most this bound we need \(2/c_2 \geq \varepsilon\) or \((\alpha(3d_\Phi+3)+2)/c_1 \geq \varepsilon\). Since we ensured the former does not hold it must be the latter that holds. Simplifying it we get \(\varepsilon\leq (3\alpha(d_\Phi+1)+4)/(d-3)\). ◻
In other words the best depth-\(d\) lower bound you can hope to prove with a natural property of depth \(d_\Phi\) and size \(2^{n^\alpha}\) is of the form \(2^{n^{O(\alpha d_\Phi/d)}}\). Hence in order to prove natural lower bounds for large subexponential sizes (i.e. \(2^{n^{\beta/d}}\) for a large beta) it is necessary that the depth of the property \(d_\Phi\) increases to a larger constant or the parameter \(\alpha\) in the size becomes larger. In the next section we show a stronger statement: even increasing to larger constant depths will not help.
We will now show PRFs of constant depth \(d\) and subexponential size (of the form \(2^{n^{O(1/d)}}\)) that fool all of \({\mathsf {AC}}_0\). It follows that no \({\mathsf {AC}}_0\)-natural property can get depth-\(d\) size lower bounds better than \(2^{n^{\Omega(1/d)}}\). In fact, this is true even for properties computable by super-constant depth \((\log n)^{\Omega(1)}\) and quasipolynoimal size \(2^{n^{O(1)}}\)! See 8 for a formal statement with the precise bounds.
At a high level our PRF is built in a similar manner to the Ajtai-Wigderson [12] PRG that fools \({\mathsf {AC}}_0\) circuits. Our construction uses two main ingredients: a PRG that fools small-depth decision trees, and a distribution on pseudorandom restrictions that collapses constant depth circuits to small-depth decision trees. These ingredients are combined using the “Ajtai-Wigderson framework” as described in the survey by Hatami and Hoza [7]. We state the framework adapted to our use case below.
In the rest of this section we will be using \(N\) to represent both \(2^n\) and we will overload notation to also let \([N]\) represent \(\mathop{\mathrm{\{0, 1\}}}^n\). The notation \([u \in W]\) represents a bit that is \(1\) if and only if \(u \in W\).
Lemma 5. [The Ajtai-Wigderson Framework, adapted] Let \(\mathop{\mathrm{\mathcal{C}}}\) be a class of circuits closed under restrictions and \(\mathop{\mathrm{\mathcal{C}}}'\) be a class of circuits perfectly fooled by a PRG \(G'\). Let \(\mathcal{W}\) be a distribution on subsets of \([N]\) such that
for all \(u\in [N]\), \(\Pr_{W \sim \mathcal{W}}[u \in W] \leq 1-p\), and
for all \(C:\mathop{\mathrm{\{0, 1\}}}^N \to \mathop{\mathrm{\{0, 1\}}}\in \mathop{\mathrm{\mathcal{C}}}\), \(\Pr_{W \sim \mathcal{W},X \sim \{0,1\}^N}[C|_{W \mapsto X} \in \mathop{\mathrm{\mathcal{C}}}'] \geq 1-\epsilon^*\).
Let \(\ell = 1/p \cdot \ln (N/\epsilon^*)\). Then there is a PRG \(G\) that \((\ell+1)\epsilon^*\)-fools \(\mathop{\mathrm{\mathcal{C}}}\).
Furthermore if every string \(X\) generated by \(G'\) has a depth-\(d\) size-\(s\) circuit computing \(u \mapsto X_u\), and every set \(W\) generated by \(\mathcal{W}\) has a depth-\(d\) size-\(s\) circuit computing \(u \mapsto [u \in W]\), then for every output \(Z\) of \(G\) there is a depth-\((d+2)\) size-\(O(s\ell)\) circuit computing \(u \mapsto Z_u\).
Proof. The PRG \(G\) is constructed as follows. Sample \(W^{(1)},\dots,W^{(\ell)}\) independently from \(\mathcal{W}\) and \(X^{(1)},\dots,X^{(\ell)}\) independently from \(G'\). Let \(\rho_i\) denote the restriction \(\overline{W^{(i)}} \mapsto X^{(i)}\) and \(\rho_{\ell+1} := [N] \mapsto 0^N\). Output \(Z \in \{0,1\}^N\) defined by the restriction \(\rho_1\rho_2\cdots\rho_{\ell}\rho_{\ell+1}\).
The correctness of the PRG is covered in the survey [7] Theorem 5.21. The circuit construction for computing \(u \mapsto Z_u\), assuming we have computed each \(X^{(i)}_u\) and each \([u \in W^{(i)}]\), is shown in 1. Since \(Z_u = X^{(i^*)}_u\) for the first index \(i^* \in [\ell+1]\) such that \(u \not\in W^{(i^*)}\), the circuit computes \(X^{(i)} \wedge (\wedge_{j < i} [u \in W^{(j)}]) \wedge [u \not\in W^{(i)}]\). Finally an \(\mathsf{OR}\) is taken over all \(i\). The negations do not add to the depth of the circuit since they can be pushed to the inputs with only a blowup of \(2\) in the overall size of the circuit. ◻
=[fill=white, draw=black, shape=circle] =[fill=white, draw=black, shape=rectangle,minimum width=0.8cm,minimum height=0.8cm,inner sep=5pt]
=[-, line width=2.5pt] =[-, dashed] =[-, dotted]
Figure 1: The circuit construction for the PRG from 5..
Our goal is to create a PRF that \(\epsilon\)-fools depth-\(d_{\Phi}\) size-\(S_{\Phi}\) circuits, and so this is our class \(\mathop{\mathrm{\mathcal{C}}}\). The class \(\mathop{\mathrm{\mathcal{C}}}'\) will be decision trees of depth \(4 \log S_{\Phi}\), which are perfectly fooled by any \((4 \log S_{\Phi})\)-wise independent PRF \(G'\). All that is left for us to do is to provide the distribution \(\mathcal{W}\) that simplifies \(\mathop{\mathrm{\mathcal{C}}}\) to \(\mathop{\mathrm{\mathcal{C}}}'\) as described in 5, and to show that both \(G'\) and \(\mathcal{W}\) have efficient constant depth circuits, which we will do in 5.1.
For the distribution \(\mathcal{W}\) we will use the derandomized switching lemma by Trevisan and Xue [11]. We describe this lemma below, but first we need a tool to generate biased random restrictions from unbiased random strings.
Definition 9. Let \(q \in \mathbb{N}\), and let \(\tau : \{0,1\}^q \times \{0,1\}\to \{0,1,*\}\) be defined as \[\tau : (x,b) \mapsto \begin{cases} * \text{ if }\wedge_{i \in [q]} x_i \\ b \text{ otherwise.} \end{cases}\] Then \(D_{q,N}^{\uparrow} : \{0,1\}^{(q+1)N} \to \{0,1,*\}^N\) is defined as \((y^{(1)},\dots,y^{(N)}) \mapsto (\tau(y^{(1)}),\dots,\tau(y^{(N)}))\).
Theorem 11 (Main Lemma (Lemma 7) in [11]). Let \(C\) be a \(M\) clause \(t\)-CNF on \(N\) bits, \(s>0\), \(q \in \mathbb{N}\) be a positive parameter and \(\mathsf{E}\) a distribution over \(\{0,1\}^{(q+1)N}\) that \(\epsilon\)-fools all \(M2^{t(q+1)}\)-clause CNFs. Then
\[\Pr_{r \sim \mathsf{E}} [\mathsf{DTdepth}(C|_{D^{\uparrow}_{q,N}(r)})>s] \leq 2^{s+t+1} (5t/2^q)^s + \epsilon \cdot2^{(s+1)(2t+\log M)}.\]
In their PRG, Trevisan and Xue use the above lemma, with the distribution \(E\) instantiated with a small-bias PRG to collapse \({\mathsf {AC}}_0\) circuits to small depth decision trees. We will do the same but with the distribution \(E\) instantiated from 10 in 4, since that gives us constant depth PRFs fooling depth 2 circuits. The collapsing of the \({\mathsf {AC}}_0\) circuit follows the same steps as when the usual switching lemma is used: A random restriction is used to make the bottom fan-in small. Then \(d-1\) random restrictions are used to decrease the depth of the \({\mathsf {AC}}_0\) circuit from \(d\) to \(2\), with the last restriction changing the depth-\(2\) circuit to a small depth decision tree.
The initial random restriction and the subsequent ones are sampled from the two distributions below respectively.
Definition 10 (Restriction-Generating Distributions). Let \(\epsilon'_0\) and \(\epsilon'_1\) be parameters to be set in 12 and 13 respectively. Distributions \({\mathsf D}_0\) and \({\mathsf D}_1\) are defined below.
A random restriction from the distribution \({\mathsf D}_0\) is sampled as follows. A string \(r\) of length \((6+1)N\) is sampled from a distribution \({\mathsf E}_0\) that \(\epsilon'_0\)-fools \(12S_\Phi\)-size CNFs. The last bit in each of the \(N\) blocks is then resampled from a uniform distribution. The restriction is then \(D_{6,N}^{\uparrow}(r)\). We will also require that \({\mathsf E}_0\) is \(6\)-wise independent.
Let \(q\) and \(t\) be parameters to be set later (in 13). A random restriction from the distribution \({\mathsf D}_1\) is sampled as follows. A string \(r\) of length \((q+1)N\) is sampled from a distribution \({\mathsf E}_1\) that \(\epsilon'_1\)-fools \(S_\Phi2^{t(q+1)}\)-size CNFs. The last bit in each of the \(N\) blocks is then resampled from a uniform distribution. The restriction is then \(D_{q,N}^{\uparrow}(r)\). We will also require that \({\mathsf E}_1\) is \(q\)-wise independent.
For simplifying some computations we will also make use of the fact that when we instantiate \({\mathsf E}_0\) and \({\mathsf E}_1\) it will be with distributions that are also \(6\)-wise and \(q\)-wise independent respectively (see the proof of 7).
Remark 1.
Since in the definition above \({\mathsf E}_0\) and \({\mathsf E}_1\) are at least \(6\)-wise and \(q\)-wise independent respectively, this guarantees that for each index \(i\), \(\rho(i)=\ast\) with probability exactly \(1/64\) if sampled from \({\mathsf D}_0\) and \(1/2^q\) if sampled from \({\mathsf D}_1\).
In the above definition the random strings \(r\) have some bits resampled at uniform. They will continue to fool CNFs after these resamplings (see [prop:foolingmanipulations]) and can hence be used in 11.
\({\mathsf E}_0\) and \({\mathsf E}_1\) are instantiated only in the proof of 7, and their \(k\)-wise independence can be verified in that proof.
With these distributions defined we can now state how we use the Ajtai-Wigderson framework.
Lemma 6. [Applying the framework] The conditions of 5 are satisfied with:
\(\epsilon^* = 8/S_{\Phi}\),
\(\mathop{\mathrm{\mathcal{C}}}\) being the class of depth-\(d_{\Phi}\) size-\(S_{\Phi}\) circuits,
\(\mathop{\mathrm{\mathcal{C}}}'\) being the class of depth-\(4\log(S_\Phi)\) decision trees and \(G'\) being a \(4\log(S_\Phi)\)-wise independent distribution,
\(p=1/(2^{O(d_{\Phi})}(\log S_{\Phi})^{d_{\Phi}-1})\), and
\(\mathcal{W}\) being the distribution of the set of restricted indices of \(\rho := \rho_0\cdots\rho_{d_\Phi-1}\) where \(\rho_0 \sim {\mathsf D}_0\) and \(\rho_i \sim {\mathsf D}_1\) for \(i>0\), with \(q=\log \log S_{\Phi}+O(1)\), \(t=4\log(S_{\Phi})\) and \(\epsilon'_1 = (2/S_\Phi^2) \cdot 2^{-60\log^2 S_\Phi}\) in the definition of \({\mathsf D}_1\).
Before we prove this we first show the purpose of the two distributions individually. First we verify that the bottom fan-ins are reduced by the first restriction. It is easy to see that this happens with a truly random restriction, the following claim shows that a pseudorandom restriction that fools CNFs would also suffice.
Claim 12. Let \(S_{\Phi} \in \mathbb{N}, \epsilon^*>0\) and set \(\epsilon'_0 := \epsilon^*/4S_{\Phi}\) in the definition of \({\mathsf D}_0\) (10). Let \(C\) be any circuit of size at most \(S_{\Phi}\). The random restriction \(\rho_0 \sim {\mathsf D}_0\) will, with probability at least \(1-\epsilon^*/2\), trivialize every bottom gate of \(C\) with fan-in larger than \(1.1\log (4S_\Phi/\epsilon^*)\).
Proof. Recall that \(\rho_0\) is sampled by sampling a string \(r\) from a CNF-fooling distribution \(E\) and applying \(D^{\uparrow}_{7,N}\) to it. Our claim follows by the observation that there is a small DNF that implies that the restriction obtained from \(r\) trivializes a gate, and that the DNF itself has a high probability of being satisfied by a uniform \(r\).
Let \(g\) be an AND/OR gate with \(t\) input bits \(x_{i_1},\dots,x_{i_t}\). The gate \(g\) gets trivialized if \(\bigvee_{j \in [t]} (\rho_0(i_j) = b_j)\), where \(b_j\) is the value of the bit \(x_{i_j}\) that would trivialize \(g\). The statement \(\rho_0(i_j) = b_j\) can be written as \(\bigvee_{a \in [6]} (r^{(i_j)}_a = 0 \wedge r^{(i_j)}_7 = b_j)\) where \(r^{(i_j)}\) is the \(i_j\)th block of \(r\). Hence there is a DNF of size \(12t\) that implies that \(g\) is trivialized.
Under a uniform \(r\), the probability that any particular input bit to \(g\) is set to the trivializing \(b_j\) is \(\frac{1}{2}(1 - 1/2^6)\), so the probability that the DNF is not satisfied is \((1/2 + 1/2^7)^t < (1/2)^{t/1.1}\).
Since the actual distribution of \(r\) (i.e. \({\mathsf E}_0\)) \(\epsilon'_0\)-fools this DNF the probability that this DNF is not satisfied is at most \((1/2)^{t/1.1} + \epsilon'_0\). By a union bound over the at most \(S_\Phi\) bottom gates and substituting the value of \(\epsilon'_0\) the probability that there is a gate with fan-in more than \(1.1 \log (4S_\Phi/\epsilon^*)\) that does not trivialize is at most \(S_\Phi((1/2)^{\log (4S_\Phi/\epsilon^*)} + \epsilon^*/4S_\Phi) = \epsilon^*/2\). ◻
Now we verify that the subsequent restrictions simplify the circuit. This crucially uses 11.
Claim 13. Let \(\epsilon^* \geq 8/S_{\Phi}\), and set \(\epsilon'_1 := (\epsilon^*/4S_{\Phi}) \cdot 2^{-15\log^2(8S_{\Phi}/\epsilon^*)}\), \(t=2\log(8S_\Phi/\epsilon^*)\) and \(q=\lceil\log(120\log S_{\Phi})\rceil\) in the definition of \({\mathsf D}_1\) (10).
Let \(C\) be any depth \(d_\Phi\) circuit where the bottom gates have fan-in at most \(2\log(8S_{\Phi}/\epsilon^*)\) and with at most \(S_{\Phi}\) non-bottom gates. The random restriction \(\rho \sim {\mathsf D}_1\) will, with probability at least \(1-\epsilon^*/2S_{\Phi}\), simplify every gate in \(C\) at depth \(d_\Phi-1\) to a decision tree of depth at most \(2\log(8S_\Phi/\epsilon^*)\).
Consequently the restricted circuit \(C\) can be written as a depth \(d_\Phi-1\) circuit where the depth-\((d_\Phi-1)\) gates have fan-in at most \(2\log(8S_{\Phi}/\epsilon^*)\) and with at most \(S_{\Phi}\) non-bottom gates.
Proof. The first part is a simple application of 11 with \(s=t=2\log(8S_\Phi/\epsilon^*)\) and \(q=\lceil\log(120\log S_{\Phi})\rceil\) and a union bound on the at most \(S_{\Phi}\) gates at depth \(d_\Phi-1\). These parameters do require \(\epsilon^* \geq 8/S_{\Phi}\) in order to work.
The second part is a routine application of the switching lemma: Gates at depth \(d_\Phi-2\) are now an AND/OR of \(2\log(8S_{\Phi}/\epsilon^*)\)-depth decision trees. These decision trees can be written both as a CNF and a DNF of width \(2\log(8S_{\Phi}/\epsilon^*)\). Hence the gates at depth \(d_\Phi-2\) can be written as either a CNF or a DNF of width \(2\log(8S_{\Phi}/\epsilon^*)\). ◻
Proof of 6. That \(G'\) perfectly fools \(\mathop{\mathrm{\mathcal{C}}}'\) is folklore. For a \(C \in \mathop{\mathrm{\mathcal{C}}}\) using 12 and 13 we see that the restriction \(\rho\) will with probability \(\geq 1-\epsilon^*\) simplify \(C\) to a decision tree of depth at most \(2\log(8S_\Phi/\epsilon^*)\leq 4\log(S_\Phi)\). Since the definition of these restrictions have the bit values resampled to be truly random and independent of the locations, the locations to be restricted satisfy the condition in 5. Let \(W\) be the indices of bits restricted by \(\rho\). In order to have \(u \not\in W\), it must not have been restricted by any of \(\rho_0\) to \(\rho_{d-1}\), which would happen with probability \(p=2^{-q(d_{\Phi}-1)}/64 \leq 2^{O(d_{\Phi})}(\log S_{\Phi})^{d_{\Phi}-1}\). ◻
5 now gives us the PRG that we need. We now analyze its locality as a constant depth PRF.
Since the distinguishers we are interested in have size between \(2^n\) and \(2^{2^n}\), we will always assume \(\log S_\Phi \geq n\) and \(\log \log S_\Phi \leq n\).
[lemma:aw,lemma:awapplied] reduce the construction of our main PRF to the construction of the PRF \(\mathcal{W}\) and of a PRF computing a \(4\log(S_\Phi)\)-wise independent distribution \(G'\). The latter is a direct corollary of 8 and 9.
Corollary 6. For every \(c_1,c_2 \in \mathbb{N}\) there is a \((n,c_1+c_2+2,2^{\tilde{O}(\log(S_\Phi) n^2)^{1/c_1}+n^{2/c_2}})\)-function generator whose output is \(4\log S_\Phi\)-wise independent.
Lemma 7. For every \(c_1,c_2 \in \mathbb{N}\) and every \(W\) in the support of \(\mathcal{W}\) there are circuits of depth \(c_1+c_2+2\) and size \(d_\Phi2^{\tilde{O}(\log^3(S_\Phi)n^2)^{1/c_1}+n^{2/c_2}}\) that compute \(u \mapsto [u \in W]\).
Proof. From 6 we see that \(W\) is built by composing together a restriction from \({\mathsf D}_0\) along with \(d_\Phi-1\) restrictions from \({\mathsf D}_1\) to get a restriction \(\rho\), and taking the set of indices that are restricted in \(\rho\).
\({\mathsf D}_0\) and \({\mathsf D}_1\) in turn are built from \({\mathsf E}_0\) and \({\mathsf E}_1\) (see 10). Since \({\mathsf E}_1\) fools larger CNFs to a larger extent, we will replace \({\mathsf E}_0\) with a marginal of \({\mathsf E}_1\) and so we will focus only on circuits implementing \({\mathsf E}_1\). \({\mathsf E}_1\) outputs strings of length \((q+1)N\) where \(q=\log \log S_\Phi+O(1) \leq n + O(1)\). We will view it as a PRF on \(n + \lceil \log (q+1) \rceil = n(1+o(1))\) input bits so that it outputs at least \((q+1)N\) bits. Recall (from 10 and 6) that \({\mathsf E}_1\) must fool \(S_\Phi2^{t(q+1)}\)-size CNFs to within error \(\epsilon'_1 = (2/S_{\Phi}^2) \cdot 2^{-60\log^2 S_{\Phi}} \leq 2^{-O(\log^2 S_{\Phi})}\). Substituting the values of \(t\) and \(q\) it needs to fool \(2^{O(\log S_\Phi \log \log S_\Phi)}\)-size CNFs.
We use 10 with the following parameters (since that uses the same named parameters that our current lemma uses, we will refer to its parameters as \(n',c_1',c_2',d_\Phi',S_\Phi'\) and \(\epsilon'\)): \(n' = n + \lceil \log (q+1) \rceil\), \(c_1' = c_1\), \(c_2'=c_2\), \(d_\Phi' = 2\), \(S_\Phi' = 2^{O(\log S_\Phi \log \log S_\Phi)}\) and \(\epsilon' = 2^{-O(\log^2(S_{\Phi}))}\). It gives us the PRF \({\mathsf E}_1\) supported on truth tables of circuits of depth \(d=c_1+c_2+2\) and size \(S=2^{\tilde{O}(\log^3(S_\Phi)n^2)^{1/c_1}+n^{2/c_2}}\). Note that from the proof of 10 the PRF is a \(k\)-wise independent distribution for \(k \geq \log^3 S_\Phi \gg q\), so \({\mathsf E}_1\) satisfies the matching condition in its definition. Furthermore since 10 directly uses [evalPoly] we know that the top gates in the circuits we use for \({\mathsf E}_1\) are all \(\mathsf{AND}\) gates.
For any output \(r\) of \({\mathsf E}_1\) the restriction from \({\mathsf D}_1\) is simply \(\rho' = D_{q,N}^{\uparrow}(r)\) (albeit with one bit in each of the \(N\) blocks of \(r\) resampled after, which in this case means it is fed directly from the seed). The value of \([\rho'(u)=\ast]\) is the same as the \(\mathsf{AND}\) of the other \(q\) bits in the \(u\)th block. That is, if \(C\) implements the PRF for \(\sf{E_1}\), it is \(\wedge_{i \in [q]} C(u,i)\).
Now \(\rho\) is a composition of \(d_\Phi\) restrictions sampled from \({\mathsf D}_0\) and \({\mathsf D}_1\). The value of \([\rho(u)=\ast]\) is the same as the \(\mathsf{AND}\) of \([\rho_i(u)=\ast]\) for each of the constituent restrictions. Since \({\mathsf E}_1\) is implemented as a local PRF generated by depth-\(d\) size-\(S\) circuits, there is a depth-\(d\) size-\(d_\Phi S\) circuit computing the map \(u \mapsto [\rho(u)=\ast]\), which is the same as \([u \in W]\). Since all we have done is added \(\mathsf{AND}\) gates on top of a layer of \(\mathsf{AND}\) gates there is no increase in depth. ◻
Combining the above with 5 we get the local PRF we were after.
=[fill=white, draw=black, shape=circle] =[fill=white, draw=black, shape=rectangle,minimum width=0.8cm,minimum height=0.8cm,inner sep=5pt]
=[-, line width=2.5pt] =[-, dashed] =[-, dotted]
Figure 2: The construction of a circuit that on input \(u \in \mathop{\mathrm{\{0, 1\}}}^n \equiv [N]\) computes \([u \in W]\) (see 7). Here the circuit \(G^0\), on input \(u\) and a seed, computes the \(u\)th part of the corresponding string \(r \in \mathop{\mathrm{\{0, 1\}}}^{(6+1)N}\) in the support of \({\mathsf E}_0\). Similarly the circuit \(G^1\), on input \(u\) and a seed, computes the \(u\)th part of the corresponding string \(r \in \mathop{\mathrm{\{0, 1\}}}^{(q+1)N}\) in the support of \({\mathsf E}_1\). We ensure that both circuits \(G^0\) and \(G^1\) have a top layer of \(\mathsf{AND}\) gates, so there is no increase in depth in this figure..
Corollary 7. Let \(c_1,c_2 \in \mathbb{N}\). There is a \((n,d,S,d_\Phi,S_\Phi)\)-PRF where \(d=c_1+c_2+4\) and \(S=2^{O(d_\Phi)}(\log S_\Phi)^{d_\Phi}2^{\tilde{O}(\log^3(S_\Phi)n^2)^{1/c_1}+n^{2/c_2}}\). From 1 this also means that there is no \((n,d,S,d_\Phi,S_\Phi)\)-natural proof.
Finally we analyze the implications for natural proofs. We see what parameters \(d_\Phi,S_\Phi\) are needed to get a \(2^{n^\varepsilon}\) lower bound for depth \(d\) circuits.
Corollary 8. Let \(d \in \mathbb{N}, d \geq 7\). There is no constant depth (or even a \(\log \log\)-depth) and polynomial size \({\mathsf {AC}}_0\) property that can yield a natural proof lower bound larger than \(2^{n^{7/(d-5)}}\) for circuits of depth \(d\).
More generally, let \(\varepsilon\in (0,1), \varepsilon\geq 2/(d-6)\). Let \(\Phi = \{\Phi_n : \mathop{\mathrm{\{0, 1\}}}^{2^n} \rightarrow \mathop{\mathrm{\{0, 1\}}}\}\) be a family of \((n, d, 2^{n^\varepsilon}, d_{\Phi}, S_{\Phi}, 8/S_\Phi)\)-natural properties. If \(S_\Phi \leq 2^{n^\alpha}\), then either \(d_\Phi \geq n^\varepsilon/(\alpha \log n)\) or \(\varepsilon\leq (3\alpha+4)/(d-5)\).
Proof. We start by proving the more general case. Set \(c_2 = \lceil2/\varepsilon\rceil \leq 2/\varepsilon+1\). Now \(c_1 = d-c_2-4\geq d-2/\varepsilon-5\). We know such a choice is possible because \(\varepsilon\geq 2/(d-6)\).
If \(S_\Phi \leq 2^{n^\alpha}\), then by 7 the maximum lower bound provable is at most \(2^{O(d_\Phi)}n^{\alpha d_\Phi} \cdot 2^{\tilde{O}(n^{3\alpha+2})^{1/c_1}+n^{2/c_2}}\). For \(2^{n^\varepsilon}\) to be at most this bound we need \(\alpha d_\Phi \log n \geq n^\varepsilon\), \(2/c_2 \geq \varepsilon\) or \((3\alpha+2)/c_1 \geq \varepsilon\). We have ensured that \(2/c_2 < \varepsilon\). Simplifying the other two conditions we get that either \(d_\Phi \geq n^\varepsilon/(\alpha \log n)\) or \(\varepsilon\leq (3\alpha+4)/(d-5)\).
For the last part a polynomial size property has \(S_\Phi = 2^{O(n)}\) and so we can substitute \(\alpha=1\). ◻
Here we will propose a concrete PRF, which is computable by depth-\(d\) circuits of size \(2^{\tilde{O}(n^{\frac{1}{d-1}})}\), and conjecture that it is secure against \({\mathsf {AC}}_0\) distinguishers. We also discuss the possibility that variants of it may be secure against all efficient distinguishers (not just \({\mathsf {AC}}_0\) distinguishers). If this is indeed the case, then it follows that the state of the art in constant-depth circuit lower-bounds cannot be improved by any natural proof.
The construction is very simple, it is based on composition of randomly-chosen functions:
Definition 11. Let \({\mathsf{Bal}}_m\) denote the set of all balanced Boolean functions \(H:\{0,1\}^m\to\{0,1\}\), meaning functions such that \(|H^{-1}(1)| = |H^{-1}(0)|\). Let \(H_{m}\) denote a random function sampled uniformly from \(\mathsf{Bal}_m\). Let \(H_{n,m}\) denote a random Boolean function over \(\{0,1\}^n\) sampled according to the following procedure:
Sample some set \(S \subseteq [n]\) of size \(m\), uniformly at random.
Sample a random Boolean function \(H_m:\{0,1\}^m\to\{0,1\}\) uniformly from \({\mathsf{Bal}}_m\).
Then set \(H_{n,m}(x) = H_m(x|_S)\) for all \(x\).
Finally, let \(F_{d,n,m}\) denote a random function \(F_d:\{0,1\}^n\to\{0,1\}\), whose distribution we define inductively as follows.
For \(d = 2\), we sample \(F_{2,n,m}(x) = H_{n,m}(x)\).
Then for \(d \ge 3\) we define \(F_{d,n,m}\) by block composition: \[F_{d,n,m}(x)= H_m(F_{d-1,n,m}(x), \dots, F_{d-1,n,m}(x)),\] i.e. we sample \(H_m\) and feed into it \(m\) independently-sampled copies of \(F_{d-1,n,m}\).
We then use \(F_{d,n}\) to denote a random function \(F_{d,n,m}\) where \(m = \tilde{O}(n^{\frac{1}{d-1}})\). If one wishes to be more concrete, one may use \(m = (\log n)^2\cdot n^{\frac{1}{d-1}}\).
Notice that \(F_{d,n}\) is a Boolean function on \(\tilde{O}(n)\) bits. By composing the DNF/CNF representations of each individual \(H_m\) and \(H_{n,m}\), we find that \(F_{d,n}\) is computable by a depth-\(d\) circuit of size \(S = 2^{\tilde{O}(n^{\frac{1}{d-1}})}\). We conjecture it is secure:
Conjecture 14. The distribution of \(F_{d,n}\) is a function generator that fools all \({\mathsf {AC}}_0\) distinguishers.
It follows as a consequence of this conjecture that \({\mathsf {AC}}_0\) natural proofs, such as proofs based on the Switching Lemma, cannot show a \(2^{\tilde{\omega}(n^{\frac{1}{d-1}})}\)-size lower-bound against depth-\(d\) circuits. Security against \({\mathsf {AC}}_0\)-distinguishers is something which one might hope to prove unconditionally, and so we consider this conjecture to be an interesting open problem.
One may also wonder whether such superexponential lower bounds can be proven even using properties outside of \({\mathsf {AC}}_0\), say computable in polytime. The above class of distributions, at least in the case \(d=3\), can actually de distinguished from random by polytime tests. However if one were to modify the definition of \(F_{3,n}(x)\) to \(H_{m}(G_1(x),\dots,G_m(x))\) with half of the \(G_i\)s being uniformly random functions of a random \(m\) of the \(n\) inputs, and the other half being parities of a random \(m\) of the \(n\) input bits, then we are unable to find polytime tests that distinguish it from random. We find it interesting to know to what extent we can show that polytime tests distinguish depth-3 size-\(2^{O(\sqrt{n})}\) distributions from uniform. Not being able to distinguish them would be akin to saying that there are PRGs in this bounded depth circuit class (and hence a natural-proofs barrier), and so we consider pushing this boundary to also be a worthwhile task.
The main problem which we leave open is an exact answer to 1. Concretely, prove or disprove whether there are PRFs computable by depth-3 circuits of size \(2^{O(\sqrt{n})}\) fooling \({\mathsf {AC}}_0\) distinguishers. Furthermore, we believe it is worthwhile to consider other models of computation and try to construct unconditional efficient PRFs computable in size close to the best known lower bounds. In 3 we also looked at some constant depth lower bound proofs that we couldn’t find natural variants for. We consider finding such variants to be another interesting open problem.
We thank Luís Pereira for pointing out a proof in the literature that we could not naturalize. We also thank anonymous reviewers whose comments helped us improve the presentation.
We stated this folklore proposition about PRFs.
Proof. The first item is true since if an algorithm in \(\mathcal{A}\) can distinguish a marginal of \(\mu_1\) from uniform, it can be used as-is to distinguish \(\mu_1\) from uniform.
The second item is a classic use case of the hybrid argument. Note that for any algorithm \(A \in \mathcal{A}\), we have that \(A\) cannot distinguish \(\mu_1 \times \mu_2\) from \(\mu_1 \times \mathsf{Unif}_{N_2}\) any better than it can distinguish \(\mu_2\) from \(\mathsf{Unif}_{N_2}\): \[\begin{align} \left| \mathop{\mathbb{E}}_{X \sim \mu_1} \mathop{\mathbb{E}}_{Y \sim \mu_2} [A(X,Y)] - \mathop{\mathbb{E}}_{X \sim \mu_1} \mathop{\mathbb{E}}_{Y \sim \mathsf{Unif}_{N_2}} [A(X,Y)] \right| &= \left| \mathop{\mathbb{E}}_{X \sim \mu_1} \left[\mathop{\mathbb{E}}_{Y \sim \mu_2} [A(X,Y)] - \mathop{\mathbb{E}}_{Y \sim \mathsf{Unif}_{N_2}} [A(X,Y)]\right] \right|\\ &\leq \max_{X \in \mathsf{supp}(\mu_1)} \left| \mathop{\mathbb{E}}_{Y \sim \mu_2} [A(X,Y)] - \mathop{\mathbb{E}}_{Y \sim \mathsf{Unif}_{N_2}} [A(X,Y)] \right| < \epsilon_2. \end{align}\] The last inequality follows since we can hardcode the \(X\) in the algorithm \(A\) and we will have an algorithm \(A' \in \mathcal{A}\) tasked with distinguishing \(\mu_2\) from \(\mathsf{Unif}_{N_2}\). The same argument can be applied to show that \(A\) cannot distinguish \(\mu_1 \times \mathsf{Unif}_{N_2}\) from \(\mathsf{Unif}_{N_1} \times \mathsf{Unif}_{N_2}\) any better than it can distinguish \(\mu_1\) from \(\mathsf{Unif}_{N_1}\). And hence by the triangle inequality, it is \((\epsilon_1+\epsilon_2)\)-fooled by \(\mu_1 \times \mu_2\). ◻
We also needed this observation about multiplicative approximate counting.
Proof. From the well-known fact proven by Ajtai and Ben-Or [36] we know that for any \(t \in [n]\) there is a function \(\mathsf{GapCount}^+_{n,t,\varepsilon} : \{0,1\}^n \to \{0,1\}\) satisfying \[\mathsf{GapCount}^+_{n,t,\varepsilon}(x) = \begin{cases} 0 & \text{if } |x| \le t\\ 1 & \text{if } |x| \ge t + \varepsilon\cdot n \end{cases}\] that can, for any \(d \ge 2\), be computed by a circuit of depth \(d+1\) and size \(O\left(n^2 \cdot 2^{\tilde{O}\left(\left(\frac{\log n}{\varepsilon^2}\right)^{1/(d-1)}\right)}\right)\). We include a proof of this as 15 for completeness.
Using this we can show that for any threshold \(t\) and approximation \(\varepsilon\in [0,1]\) we can build a slightly larger circuit computing \(\mathsf{GapCount}^{\times}_{n,t,\varepsilon}\). We start by padding the input to length \(n'\) with 0s, so that \(t/n' < \varepsilon/10\). Now consider an OR gate \(v\) over \(\lceil\frac{n'}{t}\rceil\) coordinates from \([n']\), chosen at random with replacement. Then: \[\begin{align} |x| \le t & \implies \Pr[v(x) = 0] = \left(1 - \frac{|x|}{n'}\right)^{\frac{n'}{t}} \ge \left(1 - \frac{t}{n'}\right)^{\frac{n'}{t}} \ge \frac{1}{e} - \frac{t}{en'}\\ |x| \ge (1 + \varepsilon) \cdot t & \implies \Pr[v(x) = 0] = \left(1 - \frac{|x|}{n'}\right)^{\frac{n'}{t}} \le \left(1 - (1+\varepsilon) \cdot\frac{t}{n'}\right)^{\frac{n'}{t}} \le \frac{1}{e^{1+\varepsilon}} \end{align}\] Now suppose that we independently sample \(m = O(n/\varepsilon^2)\) such ORs. By Chernoff and a union bound, there is a setting of the randomness such that every \(x\) with \(|x| \le t\) will have at least \(\left(e^{-1} - t/en' - \varepsilon/10 \right)m\) such ORs set to \(0\), and every \(x\) with \(|x| \ge (1 + \varepsilon) \cdot t\) will have at most \(\left(e^{-(1+\varepsilon)} + \varepsilon/10 \right)m\) many. We have \(e^{-1} - e^{-(1+\varepsilon)} \geq \frac{\varepsilon}{e} - o(\varepsilon)\), so the two cases can now be distinguished using \(\mathsf{GapCount}^+_{m,(e^{-(1+\varepsilon)}+\varepsilon/10)m,\varepsilon/10}\).
Even with \(\varepsilon= 1/\log^r n\), there is a circuit of depth \(2r+4\) and size \(\mathsf{poly}(n)\) that computes \(\mathsf{GapCount}^+_{m,(e^{-(1+\varepsilon)}+\varepsilon/10)m,\varepsilon/10}\). By feeding this circuit the \(m\) OR gates (thus increasing the depth by \(1\) and the size by \(2m\)), we have a circuit computing \(\mathsf{GapCount}^{\times}_{n,t,\varepsilon}(x)\) as well. ◻
Claim 15. There is a function \(\mathsf{GapCount}^+_{n,t,\varepsilon} : \{0,1\}^n \to \{0,1\}\) satisfying \[\mathsf{GapCount}^+_{n,t,\varepsilon}(x) = \begin{cases} 0 & \text{if } |x| \le t\\ 1 & \text{if } |x| \ge t + \varepsilon\cdot n \end{cases}\] that can, for any \(d \ge 2\), be computed by a circuit of depth \(d+1\) and size \(O\left(n^2 \cdot 2^{\tilde{O}\left(\left(\frac{\log n}{\varepsilon^2}\right)^{1/(d-1)}\right)}\right)\).
The proof provided below follows a manuscript by Oded Goldreich [58]. Since the statement above is a bit more general we are reproducing the (essentially same) proof.
Proof. For a string \(s \in \{0,1\}^m\) let \(\mathsf{wt}(s)\) denote the fractional Hamming weight \(\frac{|\{i \in [m] \mid s_i=1\}|}{m}\).
The circuit is conceptually simple and will just be the \(\mathsf{OR}_n\) of \(\mathsf{AND}_n\)s of threshold functions on \(O((\log n)/\varepsilon^2)\) bits (or alternatively an \(\mathsf{AND}_n\) of \(\mathsf{OR}_n\)s of such functions). Since a threshold function on \(m\) bits can be computed in depth \(d\) and size \(2^{\tilde{O}\left(m^{1/(d-1)}\right)}\) ([59], or see footnote8), and by collapsing together the second and third layers, this is a depth \(d+1\) circuit of the requisite size. We will now see why such a circuit can exhibit the requisite behaviour.
There is a choice of subsets \(S_1,\dots,S_{n^2} \subseteq [n]\), each of size \(O((\log n)/\varepsilon^2)\), such that for every \(x \in \{0,1\}^n\) more than \(n^2-n\) of the sets \(S\) are “good” in that they satisfy \(|\mathsf{wt}(x)-\mathsf{wt}(x_{S})| \leq \varepsilon/3\). To see this note that if we fix any \(x\) and choose each \(S_i\) by choosing \((15\ln n)/\epsilon^2\) indices at random with replacement, by a Chernoff bound each \(S_i\) has a \(< n^{-3}\) probability of being a bad set. The probability that at least \(n\) are bad is then at most \(\binom{n^2}{n} (n^{-3})^n \leq n^{-n}\). By a union bound over all \(x\) there is a setting of \(S_1,\dots,S_{n^2}\) satisfying the property.
Hence by computing whether \(\mathsf{wt}(x_S) \geq t/n + \varepsilon/2\) for each set, we get \(n^2\) bits \(b_1,\dots,b_{n^2}\) such that the number of \(1\)s is larger than \(n^2-n\) if \(|x| \ge t + \varepsilon\cdot n\), and smaller than \(n\) if \(|x| \leq t\). This is easy to differentiate as follows. Label the bits as \(\{b_{i,j}\}_{i,j \in [n]}\). The circuit \(\vee_{i \in [n]} \wedge_{j \in [n]} b_{i,j}\) distinguishes the two cases: If there are less than \(n\) \(0\)s it must be the case that some \(\mathsf{AND}\) outputs \(1\) so the circuit must output \(1\), and if there are less than \(n\) \(1\)s every \(\mathsf{AND}\) must output \(0\) so the circuit must output \(0\). (A similar argument works using \(\wedge_{i \in [n]} \vee_{j \in [n]} b_{i,j}\) instead.) This completes the proof. ◻
Proof. Let \(n \in \mathbb{N}\). We work in the field \(\mathbb{F} = \mathbb{F}_{2^n}\). This is the same as the field \(\mathbb{F}_2[x] / p(x)\) for an irreducible \(p(x)\) of degree \(n\). The elements of \(\mathbb{F}\) are thus identified with \(\{0,1\}^n\) as just the string of coefficients.
Given as input \(\alpha^{(0)} ,\dots ,\alpha^{(k - 1)} , y \in \mathbb{F}\), we want to compute \(\sum_{i = 0}^{k - 1} \alpha^{(i)} y^i\).
Healy et al. [57] shows that computing \(y^{2^i}\) is quite easy: \(\binom{2^i}{j}\) is even for every \(j \neq 0 \text{ or } 2^i\), so if \(y = \sum y_h x^h\), then \(y^{2^i} = \sum_h y_h x^{h 2^i}\). We can store, for each \(h \in [n]\) and \(i \in [\lfloor \log k\rfloor]\), the elements \(x^{h 2^i}\). Hence \(y^{2^i}\) is the \(n\)-bit string whose \(r\)th bit is \(\oplus_{\{h : (x^{h 2^i})_r = 1\}} y_h\). Hence the circuit computing \(y \mapsto (y^1 , y^2 , y^4 ,\ldots , y^{2^{\lfloor \log k\rfloor}})\) is implemented in parallel by \(n \lfloor \log k\rfloor\) parities of arity at most \(n\) each.
Now we want to compute an element of the form \(\alpha^{(i)} y^i\). This is the multiplication of \(t \leq 1 +\lfloor \log k\rfloor\) terms: \(\alpha^{(i)}\) and the appropriate \(y^{2^j}\)s. Following [57] we compute this with a circuit for iterated multiplication of \(t\) elements \(\beta^{(1)} ,\ldots ,\beta^{(t)} \in \mathbb{F}_2[x]\), only afterwards reducing it to \(\mathbb{F}\). The iterated multiplication is done via the Discrete Fourier Transform. Let \(\widehat{\mathbb{F}} = \mathbb{F}_{2^m}\) with \(m = \lceil \log(n t)\rceil\), and let \(S \subset \widehat{\mathbb{F}}\) be a set of non-zero elements of size \((n - 1)t + 1\). It is well known that the polynomial evaluation map for degree \((n - 1)t\) polynomials, \(M : (p_h)_{h \in [0 ,\ldots ,(n - 1)t]} \mapsto (p(g))_{g \in S}\) is an invertible \(\widehat{\mathbb{F}}\)-linear map. We use this to get \((\beta^{(i)}(g))_{g \in S}\) for each \(i\). From these we define \(\beta^{\times}(g) = \prod_i \beta^{(i)}(g) \in \widehat{\mathbb{F}}\). These are the evaluations of the degree \((n - 1)t\) polynomial \(\beta^{\times} = \prod_i \beta^{(i)}\). We then use \(M^{- 1}\) to recover the \((n - 1) t + 1\) coefficients of \(\beta^{\times}\). Finally we need to reduce this to a polynomial in \(\mathbb{F}\). We explain how to do each step below.
Since \(M\) is \(\widehat{\mathbb{F}}\)-linear and the coefficients of each \(\beta^{(i)}\) are in \(\mathbb{F}_2\), \(\beta^{(i)}(g)\) is the \(m\)-bit string whose \(r\)th bit is \(\oplus_{h : (M_{g , h})_r = 1} \beta_h^{(i)}\). So from \((\beta^{(i)})_{i \in [t]}\) we compute \((\beta^{(i)}(g))_{i \in [t], g \in S}\) by parallelly using at most \(n t^2 m\) parities of arity at most \(n\).
Each bit of \(\beta^{\times}(g)\) is a function of \((\beta^{(i)}(g))_{i \in [t]}\), so each bit is a function of at most \(m t\) bits that have already been computed. To simplify the next step we will instead compute terms of the form \((M^{- 1})_{h , g} \cdot \beta^{\times}(g)\), which also depend on the same \(m t\) bits. Hence each bit can be computed by both a CNF and a DNF of size \(2^{m t}\). There are \(m n^2 t^2\) bits of output in \(((M^{- 1})_{h , g} \cdot \beta^{\times}(g))_{h \in [0 ,\ldots ,(n - 1)t], g \in S}\).
We can now recover the coefficients of \(\beta^{\times}\) from \((\beta^{\times}(g))_{g \in S}\) as \(\beta_h^{\times} = \sum_g (M^{- 1})_{h , g} \cdot \beta^{\times}(g)\). Since each \(\beta^{(i)}\) had coefficients in \(\mathbb{F}_2\), so will \(\beta^{\times}\) and so we only care about one bit of each coefficient. The relevant bit for the \(h\)th coefficient is simply \(\oplus_g (M_{h , g}^{- 1} \cdot \beta^{\times}(g))_0\), so it is a parity of arity at most \(n t\), and there are at most \(n t\) such coefficients to compute.
Finally we need to simplify the computed degree-\((n - 1)t\) polynomial \(\beta^{\times} \in \mathbb{F}_2[x]\) to its modulus in \(\mathbb{F}\). For this we simply pre-store the representations of \(x^r \in \mathbb{F}\) for each \(r \in [n ,\ldots ,(n - 1)t]\). Our final polynomial’s \(h\)th coefficient is then \(\beta_h^{\times} + \sum_{r \geq n} (x^r)_h\). This is a parity of arity at most \(n t\), and there are at most \(n\) of them.
Using \(k\) copies of the circuit above we construct each \(\alpha^{(i)} y^i \in \mathbb{F}\). We now sum up over all \(k\) terms to get \(\sum_{i = 0}^{k - 1} \alpha^{(i)} y^i\). This is achieved by \(n\) parallel parities of arity \(k\), and that is our output.
Looking at the above construction we get a circuit with the following layers with \(t = 1 +\lfloor \log k\rfloor\) and \(m =\lceil \log(n t)\rceil\):
\(n\) \(\oplus_k\) gates,
\(k n\) \(\oplus_{n t}\) gates,
\(k n t\) \(\oplus_{n t}\) gates,
\(k n^2 t^2 m\) CNFs of size \(2^{m t}\),
\(k n t^2 m\) \(\oplus_n\) gates,
\(k n \lfloor \log k\rfloor\) \(\oplus_n\) gates.
This simplifies to a top layer of \(n\) \(\oplus_{k n^2 t^2}\) gates, a middle layer of \(k n^2 t^2 m\) CNFs of size \(2^{m t}\), and a bottom layer of \(k n t\) \(\oplus_{n^2}\) gates.
Using unbounded arity AND/OR gates we can implement this in constant depth as follows. For any \(c \in \mathbb{N}\) the parity of \(s\) bits can be computed in depth \(c+1\) and size \(s2^{s^{1/c}}\). Such circuits exist with an \(\mathsf{AND}\) gate at the top and they also exist with an \(\mathsf{OR}\) gate at the top. We implement the top layer of parities in depth \(c_1+ 1\) and size \(\mathsf{poly}(k,n) 2^{(k n^2 t^2)^{1/c_1}}\) with \(\mathsf{AND}\) gates at the top. For each input literal to the parity circuit we can attach a CNF/DNF of the middle layer appropriately so that the top gate of the CNF/DNF merges with the gate that the literal fed in to. The circuit now has depth \(c_1+2\) and size \(2^{m t} \cdot n 2^{(k n^2 t^2)^{1/c_1}}\). Finally for every input literal of this circuit we attach a depth \(c_2+1\) size \(n^2 2^{n^{2/c_2}}\) parity circuit computing said input, choosing the parity circuit appropriately so that the top gate of the parity merges with the gate that the literal fed in to. Since \(2^{m t} \leq 2^{\tilde{O}(nk)}\), for any fixed constants \(c_1,c_2 \in \mathbb{N}\) the final circuit is of depth \(c_1 + c_2 + 2\) and size at most \[\mathsf{poly}(k,n) 2^{m t} \cdot \left(n \cdot 2^{(kn^2t^2)^{1/c_1}} + k n t \cdot 2^{n^{2/c_2}}\right) \leq 2^{\widetilde{O}(kn^2)^{1/c_1} + n^{2/c_2}}.\] ◻
arXiv:1009.0246, 2010.arXiv:1701.01717, 2017.LASIGE, Faculdade de Ciências, Universidade de Lisboa, Portugal. Funded by the European Union (ERC, HOFGA, 101041696). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European
Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Also supported by FCT through the LASIGE Research Unit, ref. UID/00408/2025. Emails:
bruno.loff@gmail.com, suhail.sherif@gmail.com, fr.ugazio@gmail.com↩︎
University of Sheffield, Sheffield, United Kingdom. Supported by Royal Society International Exchanges Grant IES\R3\243239. Email: n.talebanfard@sheffield.ac.uk↩︎
Constructions of candidate PRFs in depth \((1+\epsilon)\log n\) can be found in the literature (see for example [6]), but these are PRFs with a different notion of security. They rely on the distinguisher only being able to make polynomially many queries to the truth table, and our distinguishers are allowed to read the whole truth table.↩︎
One should contrast this kind of complexity-theoretic PRF with a cryptographic PRF. In [8], the authors construct a PRF computable in \({\mathsf {AC}}_0\) which fools \({\mathsf {AC}}_0\) distinguishers that are given a polynomially-long sequence of randomly-sampled input-output pairs \((x, f(x))\). Such distinguishers are exponentially weaker than the distinguishers we aim to fool: in our case the \({\mathsf {AC}}_0\) distinguisher has access to the entire truth-table, not just a small number of samples.↩︎
What it does rule out is a property like the one from the Switching Lemma, which was always a poly-size property of a fixed depth, from simultaneously proving a \(2^{n^{\omega(1/d)}}\) lower bound on depth \(d\) circuits for all large enough \(d\).↩︎
See the discussion in the “Connections with MCSP” section of the Introduction for a comparison with another work that also uses a localization (but not in constant depth) of the Trevisan–Xue switching lemma.↩︎
It should be understood that \(d_\Phi\) and \(S_\Phi\) are not somehow indexed by \(\Phi\), it is just convenient to use the subscript \(\Phi\) to reinforce that \(d_\Phi\) and \(S_\Phi\) are the depth and sizes of the distinguisher, as opposed to the depth \(d\) and size \(S\) of the function whose complexity is being lower-bounded.↩︎
Consider the function \(f_k : (\{0,1\}^{\lceil \log m \rceil})^{k} \to \{0,1\}^{\lceil \log m \rceil}\), where the inputs are interpreted as \(a_1,\dots,a_k \in [m]\), that computes \(\sum_{i \in [k]} a_i\) (with the promise that the sum is always at most \(m\)). Since there are only \(k\lceil\log m\rceil\) input bits, each output bit of the function can be written as an \(\mathsf{OR}\) of \(\mathsf{AND}\)s of literals (or an \(\mathsf{AND}\) of \(\mathsf{OR}\)s of literals) of size \(2^{k \lceil \log m \rceil}\). By composing together \(d-1\) layers of \(f_k\) with \(k = m^{1/(d-1)}\) we get a function that computes the exact count of \(1\)s present in \(m\) input bits. Replace the top \(f_k\) with a similarly sized function that outputs \(1\) iff \(\sum a_i > c\) to make the composition a threshold function. Choosing circuits for each instance of \(f_k\) to make \(\mathsf{OR}\)s and \(\mathsf{AND}\)s collapse, we obtain a circuit of depth \(d\) and size \(O(m \cdot \log m \cdot 2^{k \lceil \log m \rceil})\).↩︎