The approximate degree of DNF and CNF formulas

The approximate degree of a Boolean function f : 0, 1 n → 0, 1 is the minimum degree of a real polynomial p that approximates f pointwise: |f (x) -p(x)| 1/3 for all x ∈ 0, 1 n . For every δ > 0, we construct CNF and DNF formulas of polynomial size with approximate degree Ω(n 1-δ ), essentially matching the trivial upper bound of n. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits (AC 0 ), a question that has seen extensive research over the past 10 years. Prior to our work, an Ω(n 1-δ ) lower bound was known only for AC 0 circuits of depth that grows with 1/δ (Bun and Thaler, FOCS 2017). Furthermore, the CNF and DNF formulas that we construct are the simplest possible in that they have constant width. Our result holds even for one-sided approximation: for any δ > 0, we construct a polynomial-size constant-width CNF formula with one-sided approximate degree Ω(n 1-δ ).

Our work has the following consequences. (i) We essentially settle the communication complexity of AC 0 circuits in the bounded-error quantum model, k-party number-on-the-forehead randomized model, and k-party number-on-the-forehead nondeterministic model: we prove that for every δ > 0, these models require Ω(n 1-δ ), Ω(n/4 k k 2 ) 1-δ , and Ω(n/4 k k 2 ) 1-δ , respectively, bits of communication even for polynomial-size constant-width CNF formulas. (ii) In particular, we show that the multiparty communication class coNP k can be separated essentially optimally from NP k and BPP k by a particularly simple function, a polynomial-size constant-width CNF formula. (iii) We give an essentially tight separation, of O(1) versus Ω(n 1-δ ), for the one-sided versus two-sided approximate degree of a function; and O(1) versus Ω(n 1-δ ) for the one-sided approximate degree of a function f versus its negation ¬f .

Our proof departs significantly from previous approaches and contributes a novel, number-theoretic method for amplifying approximate degree.

• This manuscript is a much-expanded version of the STOC '22 paper, with several new results.