The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $\delta>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $\Omega(n^{1-\delta}),$ 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 ($\text{AC}^{0}$), a question that has seen extensive research over the past 10 years. Prior to our work, an $\Omega(n^{1-\delta})$ lower bound was known only for $\text{AC}^{0}$ circuits of depth that grows with $1/\delta$ (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 $\delta>0$, we construct a polynomial-size constant-width CNF formula with one-sided approximate degree $\Omega(n^{1-\delta})$.

Our work has the following consequences.

(i) We essentially settle the communication complexity of $\text{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 $\delta>0$, these models require $\Omega(n^{1-\delta})$, $\Omega(n/4^{k}k^{2})^{1-\delta}$, and $\Omega(n/4^{k}k^{2})^{1-\delta}$, respectively, bits of communication even for polynomial-size constant-width CNF formulas.

(ii) In particular, we show that the multiparty communication class $\text{coNP}_{k}$ can be separated essentially optimally from $\text{NP}_{k}$ and $\text{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 $\Omega(n^{1-\delta})$, for the one-sided versus two-sided approximate degree of a function; and $O(1)$ versus $\Omega(n^{1-\delta})$ for the one-sided approximate degree of a function $f$ versus its negation $\neg f$.

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