Results on restricted CNFs, sparse partitions, hard slices and depth-three circuits, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Depth-three lower bound beyond every square-root constant (OpenAI) — Theorem 2.1. One polynomial-time language whose membership functions need OR-AND-OR circuits with more than 2^(A sqrt n) gates, for every constant A and every large n.
• Averaging over restrictions — Lemma 4.1. The correlation of two functions on the cube is the average, over random restrictions, of the correlation of the restricted functions.
• Restriction bound (OpenAI) — Lemma 1.1. After a p-random restriction, a CNF of width k correlates with any function at most W times that function's best correlation with CNFs of width b, where the expectation of W is at most 1/(1-theta), whatever the number of clauses.
• Paths — Lemma 3.1. A path of clauses that are wide when chosen has bounded length and distinct indices, and its violated clauses are counted at every later step.
• Peeling — Lemma 4.1. The remaining correction of a path equals its term minus the remaining corrections of its one-step extensions.
• Finite expansion — Proposition 5.1. A restricted CNF equals a narrow CNF plus a finite alternating sum of path fractions.
• Marker mixture — Lemma 1.1. The conjunction of the clauses before the first of c markers in a random order holds with probability c/(c+w) at a point violating w of the clauses.
• Path terms as averages — Lemma 3.1. Each path term is a positive weight times an average of CNFs of width at most b.
• Reweighting — Lemma 4.1. The expected total weight of the paths of a given length equals an expectation over a full random assignment of reciprocal counts of violated clauses.
• Backward counting — Lemma 5.1. The total weight of s reverse steps from any state is at most theta^s, because each step averages over the violated clauses.
• Sparse partition — Lemma 1.1. A CNF of width b on m variables is a sum of at most 2^(eta m) CNFs of width b with disjoint supports and at most M m clauses each.
• Sunflower lemma (Erdős and Rado) — Lemma 2.1. More than s!(r-1)^s distinct sets of size s contain a sunflower with r members.
• Branching identity — Lemma 3.1. Inserting the core, or the petals with the core false, splits the conjunction into two functions with disjoint supports.
• Occurrence bound — Lemma 4.1. Without an eligible sunflower at size i, every literal lies in at most e_i clauses of size i.
• Added clauses — Lemma 4.2. At every state each literal lies in at most e_u + 1 added clauses of size u.
• Insertion budget — Lemma 5.1. The number of inserted clauses of size u is at most (e_u+1)(2m + the number of smaller insertions).
• Strings with few ones — Lemma 6.1. At most 2^(N h(x)) binary strings of length N have at most N x ones, for x at most 1/2.
• A field as a quotient — Lemma 1.1. For every r there is a monic polynomial P of degree r over the field with two elements whose quotient ring is a field.
• The parameters — Lemma 2.2. For d at least 64 the parameters r and t satisfy the stated bounds and the four blocks fit into the input.
• Deciding membership — Proposition 3.1. Membership is decided with a polynomial number of bit operations, for every monic modulus.
• Uniform hash values — Lemma 4.1. The hash of every nonzero vector is uniformly distributed.
• Injectivity — Lemma 4.2. The hash is injective on a restricted cube of dimension m except with probability at most 2^(m-r).
• Interpolation — Lemma 5.1. The values of a random polynomial of degree below t at up to t distinct points of a field are independent and uniform.
• Limited independence of a slice — Proposition 5.2. When the hash is injective on a restricted cube, the signs of a random slice there are unbiased and t-wise independent.
• Hard slices (OpenAI) — Proposition 1.1. Some setting of the parameter bits gives a slice whose sign has correlation at most 2^(-|T|/8) with every CNF of width b on most random restrictions.
• Number of sparse tests — Lemma 2.1. There are at most 2^(M m (1 + b log(2m+1))) CNFs of width b with at most M m clauses on m variables.
• Moment bound — Lemma 3.1. For t-wise independent unbiased signs and even t, the t-th moment of a signed sum over a cube of dimension m is at most t^t 2^(m t/2).
• All narrow tests — Lemma 4.1. Under a condition on m and t, a random slice has correlation at most 2^(-m/8) with every CNF of width b, except with probability 2^(-m t/8).
• Size of the live set — Lemma 5.1. The number of live variables lies between half and twice its mean except with probability 2 * 2^(-m_0/16).
• Choice of the width — Lemma 1.1. A width b depending only on A makes the parameter theta of the restriction bound at most 1/2.
• Correlation with wide CNFs — Proposition 2.1. A hard slice has correlation at most 6 * 2^(-m_0/16) with every CNF of width k.
• Balance — Corollary 2.2. A hard slice accepts at least a quarter of its inputs.
• Small circuits accept little — Proposition 3.1. A depth-three circuit with S gates computing a hard slice accepts at most a 6 S 2^(-m_0/16) + S^2 2^(-k) fraction of the inputs.
• The lower bound (OpenAI) — Theorem 4.1. For every A the language needs depth-three circuits with more than 2^(A sqrt n) gates at all large lengths n, and it is decided in polynomial time.

Reading order

Read the lessons in order; the fourth lesson on sunflowers and the sparse partition can be read on its own.