ETH False

Summary

The lecture presents an unfinished explanation of a claimed subexponential-time algorithm for #3-SAT, the problem of counting all satisfying assignments of a 3-CNF formula. The lecturer notes that such an algorithm would also solve 3-SAT in subexponential time, contradicting the Exponential Time Hypothesis (ETH). The result had appeared only days earlier, and the lecturer repeatedly cautions that he may not understand or explain every part of the proof.

The lecture develops a version for sparse formulas, where the number of clauses is linear in the number of variables. The lecturer says known sparsification methods relate this case to general 3-SAT, with some loss in the exponent, and that the cited OpenAI proof uses additional ideas to avoid that loss. The lecture does not complete the proof.

Main Proof Strategy

The central idea is to translate the counting problem into one involving matrix permanents.

The permanent is similar to the determinant, but without permutation signs. For a zero-one matrix interpreted as the adjacency matrix of a bipartite graph, its permanent counts the graph’s perfect matchings. The lecturer invokes a reduction from counting CSP solutions, including #3-SAT solutions, to computing the permanent of a sparse matrix. It would therefore suffice to compute permanents of the relevant sparse matrices faster than the usual exponential-time bound.

The proposed approach for computing the permanent of a difficult, unstructured matrix (A) is as follows:

1. Use the ordinary exponential-time algorithm as a baseline. Direct expansion takes factorial time, but memoization, dynamic programming, or Ryser’s formula computes the permanent in roughly (2^n) time.

2. Construct a low-degree polynomial family of matrices. Build (A(t)) so that (A(0)=A), while (A(i)) is easier to handle for selected nonzero integer values (i). Each entry is a low-degree polynomial in (t); the lecture describes the degree as roughly (\sqrt{\log n}), suppressing logarithmic-logarithmic factors.

3. Make the nonzero evaluations structured. For (i>0), the matrices (A(i)) are intended to have the form [ B_i+E, ] where (B_i) is block diagonal with relatively small blocks and (E) has low rank. Permanents of such matrices can be computed efficiently using:

   • the product rule for permanents of block-diagonal matrices;
   • algorithms for low-rank matrices; and
   • dynamic programming.

The same structure is retained by submatrices, which is important for computing derivatives.

1. Interpolate using values and derivatives. Let [ P(t)=\operatorname{perm}(A(t)). ] Since the permanent is a degree-(n) polynomial in the matrix entries, (P(t)) has degree at most (n) times the degree of (A(t)). The plan is to compute values of (P) and several of its derivatives at about (L\approx\log n) evaluation points. These provide linear constraints on the coefficients of (P). With enough constraints—roughly, (L) times the number of derivatives per point exceeding (\deg P)—Hermite interpolation determines (P), and hence (P(0)=\operatorname{perm}(A)).

2. Keep derivative computations affordable. The lecture says derivatives of the permanent at the structured matrices can be expressed using permanents of their submatrices. Higher derivatives are more expensive, but the proposed cost remains manageable for the required number of derivatives. With lower-order factors suppressed, the resulting estimate is described as subexponential, approximately [ 2^{O(n/\sqrt{\log n})}. ]

Where the Structure Is Meant to Come From

The lecture sketches a Boolean-function idea intended to produce the structured matrices:

• On (L) bits represented as (\pm1), parity is the product of the bits and has exact polynomial degree (L).
• Parity can be approximated on almost all inputs by a much lower-degree polynomial.
• Since parity is symmetric, the approximation can be built as a one-variable polynomial in the sum of the bits. Most uniformly random bit strings have Hamming weight near the middle, so the polynomial can match parity on those central layers while behaving arbitrarily on the relatively rare outer layers.
• The lecturer says the approximation has very small error, on the order of an inverse polynomial in (L). This small error is intended to translate into a low-rank error term in a matrix construction.
• A Hadamard/Fourier transform is then used to turn parity information into a simple anti-diagonal structure. Replacing exact parity with its low-degree approximation is intended to yield matrices that are close to block diagonal, up to low rank.

This construction is only sketched. The lecture ends before showing in detail how the approximating polynomial produces the required matrix family (A(t)) or completing the proof.

Key Takeaway

The proposed approach combines counting reductions, permanents, dynamic programming, polynomial interpolation with derivatives, low-rank matrix structure, and low-degree approximations of parity. The goal is to recover the permanent of an unstructured matrix from easier structured instances.

If the claimed subexponential algorithm for #3-SAT holds, it would imply a subexponential algorithm for ordinary 3-SAT and therefore refute ETH. The lecture is a preliminary, incomplete walkthrough—not a completed proof.

Speakers and Sources Mentioned

• Ryan O’Donnell — lecturer and principal speaker.
• Bernardo — student who asks questions and contributes a point about reductions to sparse instances.
• Other unnamed students — ask questions during the lecture.
• OpenAI / GPT — mentioned as a source of the recently appearing proof and as an AI tool the lecturer was using to help understand it.
• Named researchers or references: Valiant; Ryser; Barvinok; Razborov–Smolensky; Trevor (a video on symmetric functions).
• Other concepts or results cited: ETH; Cook–Levin; sparsification; Hermite interpolation.