pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function

f

with approximate degree

d

into a function

F

O(n \cdot \mathrm{polylog}(n))

variables with approximate degree at least

D = \Omega(n^{1/3} \cdot d^{2/3})

. In particular, if

d= n^{1-\Omega(1)}

, then

D

is polynomially larger than

d

. Moreover, if

f

is computed by a polynomial-size Boolean circuit of constant depth, then so is

F

. By recursively applying our transformation, for any constant

\delta > 0

we exhibit an AC

^0

function of approximate degree

\Omega(n^{1-\delta})

. This improves upon the best previous lower bound of

\Omega(n^{2/3})

due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of

n

that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant

\delta > 0

, an

\Omega(n^{1-\delta})

lower bound on the quantum communication complexity of a function in AC

^0

; (ii) a Boolean function

f

with approximate degree at least

C(f)^{2-o(1)}

, where

C(f)

is the certificate complexity of

f

; this separation is optimal up to the

o(1)

term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC

^0

DOI: 10.1137/17m1161737

Related papers

A Nearly Optimal Lower Bound on the Approximate Degree of AC $^0$ A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$ . We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(n \cdot \operatorname{polylog}(n))$ variables with approximate degree at least $D = Ω(n^{1/3} \cdot d^{2/3})$ . In particular, if $d= n^{1-Ω(1)}$ , then $D$ is polynomially larger than $d$ . Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$ . By recursively applying our transformation, for any constant $δ> 0$ we exhibit an AC $^0$ function of approximate degree $Ω(n^{1-δ})$ . This improves over the best previous lower bound of $Ω(n^{2/3})$ due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant $δ> 0$ , an $Ω(n^{1-δ})$ lower bound on the quantum communication complexity of a function in AC $^0$ . * A Boolean function $f$ with approximate degree at least $C(f)^{2-o(1)}$ , where $C(f)$ is the certificate complexity of $f$ . This separation is optimal up to the $o(1)$ term in the exponent. * Improved secret sharing schemes with reconstruction procedures in AC $^0$ .The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(n \cdot \operatorname{polylog}(n))$ variables with approximate degree at least $D = Ω(n^{1/3} \cdot d^{2/3})$. In particular, if $d= n^{1-Ω(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$. By recursively applying our transformation, for any constant $δ> 0$ we exhibit an AC$^0$ function of approximate degree $Ω(n^{1-δ})$. This improves over the best previous lower bound of $Ω(n^{2/3})$ due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant $δ> 0$, an $Ω(n^{1-δ})$ lower bound on the quantum communication complexity of a function in AC$^0$. * A Boolean function $f$ with approximate degree at least $C(f)^{2-o(1)}$, where $C(f)$ is the certificate complexity of $f$. This separation is optimal up to the $o(1)$ term in the exponent. * Improved secret sharing schemes with reconstruction procedures in AC$^0$.

arXiv:1703.05784Mar 16, 20170 citations

A Nearly Optimal Lower Bound on the Approximate Degree of AC^0

Mark Bun, Justin Thaler

The approximate degree of a Boolean function f : {-1, 1}n→ {-1, 1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function f with approximate degree d into a function F on O(n · polylog(n)) variables with approximate degree at least D = Ω(n1/3· d2/3). In particular, if d = n1-Ω(1), then D is polynomially larger than d. Moreover, if f is computed by a constant-depth polynomial-size Boolean circuit, then so is F. By recursively applying our transformation, for any constant δ > 0 we exhibit an AC0function of approximate degree Ω(n1-δ). This improves over the best previous lower bound of Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: · For any constant δ > 0, an Ω(n1-δ) lower bound on the quantum communication complexity of a function in AC0. · A Boolean function f with approximate degree at least C(f)2-o(1), where C(f) is the certificate complexity of f. This separation is optimal up to the o(1) term in the exponent. · Improved secret sharing schemes with reconstruction procedures in AC0.The approximate degree of a Boolean function f : {-1, 1}n→ {-1, 1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function f with approximate degree d into a function F on O(n · polylog(n)) variables with approximate degree at least D = Ω(n1/3· d2/3). In particular, if d = n1-Ω(1), then D is polynomially larger than d. Moreover, if f is computed by a constant-depth polynomial-size Boolean circuit, then so is F. By recursively applying our transformation, for any constant δ > 0 we exhibit an AC0function of approximate degree Ω(n1-δ). This improves over the best previous lower bound of Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of n that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: · For any constant δ > 0, an Ω(n1-δ) lower bound on the quantum communication complexity of a function in AC0. · A Boolean function f with approximate degree at least C(f)2-o(1), where C(f) is the certificate complexity of f. This separation is optimal up to the o(1) term in the exponent. · Improved secret sharing schemes with reconstruction procedures in AC0.

Annual Symposium on Foundations of Computer ScienceOct 1, 201719 citations

The Approximate Degree of DNF and CNF Formulas

Alexander A. Sherstov

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 $δ>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 ( $\text{AC}^0$ ), a question that has seen extensive research over the past 10 years. Previously, an $Ω(n^{1-δ})$ lower bound was known only for $\text{AC}^0$ circuits of depth that grows with $1/δ$ (Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further 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 $δ>0$ , these models require $Ω(n^{1-δ})$ , $Ω(n/4^kk^2)^{1-δ}$ , and $Ω(n/4^kk^2)^{1-δ}$ , 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. (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 $\neg f$ .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 $δ>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 ($\text{AC}^0$), a question that has seen extensive research over the past 10 years. Previously, an $Ω(n^{1-δ})$ lower bound was known only for $\text{AC}^0$ circuits of depth that grows with $1/δ$ (Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further 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 $δ>0$, these models require $Ω(n^{1-δ})$, $Ω(n/4^kk^2)^{1-δ}$, and $Ω(n/4^kk^2)^{1-δ}$, 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. (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 $\neg f$.

arXiv:2209.01584Sep 4, 20220 citations

Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

Alexander A. Sherstov, Pei Wu

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$ . Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits ( $\text{AC}^{0}$ ) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications. We give an essentially optimal solution to this problem. For any $ε>0,$ we construct an $\text{AC}^{0}$ circuit in $n$ variables that has threshold degree $Ω(n^{1-ε})$ and sign-rank $\exp(Ω(n^{1-ε})),$ improving on the previous best lower bounds of $Ω(\sqrt{n})$ and $\exp(\tildeΩ(\sqrt{n}))$ , respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of $\text{AC}^{0}$ circuits of any given depth, with a strict improvement starting at depth $4$ . As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of $\text{AC}^{0}$ , strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of $\text{AC}^{0}$ .The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits ($\text{AC}^{0}$) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications. We give an essentially optimal solution to this problem. For any $ε>0,$ we construct an $\text{AC}^{0}$ circuit in $n$ variables that has threshold degree $Ω(n^{1-ε})$ and sign-rank $\exp(Ω(n^{1-ε})),$ improving on the previous best lower bounds of $Ω(\sqrt{n})$ and $\exp(\tildeΩ(\sqrt{n}))$, respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of $\text{AC}^{0}$ circuits of any given depth, with a strict improvement starting at depth $4$. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of $\text{AC}^{0}$, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of $\text{AC}^{0}$.

arXiv:1901.00988Jan 4, 20194 citations

The Large-Error Approximate Degree of AC^0

Mark Bun, Justin Thaler

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.

Leibniz international proceedings in informaticsJan 1, 20190 citations

The Approximate Degree of DNF and CNF Formulas

Alexander A. Sherstov

Abstract. The approximate degree of a Boolean function [Formula: see text] is the minimum degree of a real polynomial [Formula: see text] that approximates [Formula: see text] pointwise: [Formula: see text] for all [Formula: see text]. For every [Formula: see text] we construct conjunctive normal form (CNF) and disjunctive normal form (DNF) formulas of polynomial size with approximate degree [Formula: see text] essentially matching the trivial upper bound of [Formula: see text]. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits [Formula: see text] a question that has seen extensive research over the past 10 years. Prior to our work, an [Formula: see text] lower bound was known only for [Formula: see text] circuits of depth that grows with [Formula: see text] (M. Bun and J. Thaler, SIAM J. Comput., 49 (2020), pp. FOCS17-59–FOCS17-96). Furthermore, the CNF and DNF formulas that we construct are the simplest possible in that they have constant width. Our proof departs significantly from previous approaches and contributes a novel, number-theoretic method for amplifying approximate degree. Our main result remains valid even for one-sided approximation: for any [Formula: see text], we construct a polynomial-size constant-width CNF formula with one-sided approximate degree [Formula: see text]. We thus obtain the following nearly tight separations: [Formula: see text] versus [Formula: see text] for the one-sided versus two-sided approximate degree of a function and [Formula: see text] versus [Formula: see text] for the one-sided approximate degree of a function [Formula: see text] versus its negation [Formula: see text]. As an application, we essentially settle the communication complexity of [Formula: see text] circuits in the bounded-error quantum model, [Formula: see text]-party number-on-the-forehead randomized model, and [Formula: see text]-party number-on-the-forehead nondeterministic model: we prove that for every [Formula: see text], these models require [Formula: see text], [Formula: see text], and [Formula: see text], respectively, bits of communication even for polynomial-size constant-width CNF formulas. In particular, we show that the multiparty communication class [Formula: see text] can be separated near-optimally from [Formula: see text] and [Formula: see text] by a particularly simple function, a polynomial-size constant-width CNF formula.Abstract. The approximate degree of a Boolean function [Formula: see text] is the minimum degree of a real polynomial [Formula: see text] that approximates [Formula: see text] pointwise: [Formula: see text] for all [Formula: see text]. For every [Formula: see text] we construct conjunctive normal form (CNF) and disjunctive normal form (DNF) formulas of polynomial size with approximate degree [Formula: see text] essentially matching the trivial upper bound of [Formula: see text]. This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits [Formula: see text] a question that has seen extensive research over the past 10 years. Prior to our work, an [Formula: see text] lower bound was known only for [Formula: see text] circuits of depth that grows with [Formula: see text] (M. Bun and J. Thaler, SIAM J. Comput., 49 (2020), pp. FOCS17-59–FOCS17-96). Furthermore, the CNF and DNF formulas that we construct are the simplest possible in that they have constant width. Our proof departs significantly from previous approaches and contributes a novel, number-theoretic method for amplifying approximate degree. Our main result remains valid even for one-sided approximation: for any [Formula: see text], we construct a polynomial-size constant-width CNF formula with one-sided approximate degree [Formula: see text]. We thus obtain the following nearly tight separations: [Formula: see text] versus [Formula: see text] for the one-sided versus two-sided approximate degree of a function and [Formula: see text] versus [Formula: see text] for the one-sided approximate degree of a function [Formula: see text] versus its negation [Formula: see text]. As an application, we essentially settle the communication complexity of [Formula: see text] circuits in the bounded-error quantum model, [Formula: see text]-party number-on-the-forehead randomized model, and [Formula: see text]-party number-on-the-forehead nondeterministic model: we prove that for every [Formula: see text], these models require [Formula: see text], [Formula: see text], and [Formula: see text], respectively, bits of communication even for polynomial-size constant-width CNF formulas. In particular, we show that the multiparty communication class [Formula: see text] can be separated near-optimally from [Formula: see text] and [Formula: see text] by a particularly simple function, a polynomial-size constant-width CNF formula.

SIAM Journal on ComputingJun 10, 20251 citation

A Nearly Optimal Lower Bound on the Approximate Degree of AC

^0

The approximate degree of a Boolean function

f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}

is the least degree of a real polynomial that approximates

f

f

with approximate degree

d

into a function

F

O(n \cdot \mathrm{polylog}(n))

variables with approximate degree at least

D = \Omega(n^{1/3} \cdot d^{2/3})

. In particular, if

d= n^{1-\Omega(1)}

, then

D

is polynomially larger than

d

. Moreover, if

f

is computed by a polynomial-size Boolean circuit of constant depth, then so is

F

. By recursively applying our transformation, for any constant

\delta > 0

we exhibit an AC

^0

function of approximate degree

\Omega(n^{1-\delta})

. This improves upon the best previous lower bound of

\Omega(n^{2/3})

due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of

n

\delta > 0

, an

\Omega(n^{1-\delta})

lower bound on the quantum communication complexity of a function in AC

^0

; (ii) a Boolean function

f

with approximate degree at least

C(f)^{2-o(1)}

, where

C(f)

is the certificate complexity of

f

; this separation is optimal up to the

o(1)

term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC

^0

A Nearly Optimal Lower Bound on the Approximate Degree of AC

^0

The approximate degree of a Boolean function

f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}

is the least degree of a real polynomial that approximates

f

pointwise to error at most

1/3

. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function

f

with approximate degree

d

into a function

F

O(n \cdot \operatorname{polylog}(n))

variables with approximate degree at least

D = Ω(n^{1/3} \cdot d^{2/3})

. In particular, if

d= n^{1-Ω(1)}

, then

D

is polynomially larger than

d

. Moreover, if

f

is computed by a polynomial-size Boolean circuit of constant depth, then so is

F

. By recursively applying our transformation, for any constant

δ> 0

we exhibit an AC

^0

function of approximate degree

Ω(n^{1-δ})

. This improves over the best previous lower bound of

Ω(n^{2/3})

due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of

n

that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant

δ> 0

, an

Ω(n^{1-δ})

lower bound on the quantum communication complexity of a function in AC

^0

. * A Boolean function

f

with approximate degree at least

C(f)^{2-o(1)}

, where

C(f)

is the certificate complexity of

f

. This separation is optimal up to the

o(1)

term in the exponent. * Improved secret sharing schemes with reconstruction procedures in AC

^0

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

δ>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 (

\text{AC}^0

), a question that has seen extensive research over the past 10 years. Previously, an

Ω(n^{1-δ})

lower bound was known only for

\text{AC}^0

circuits of depth that grows with

1/δ

(Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further 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

δ>0

, these models require

Ω(n^{1-δ})

Ω(n/4^kk^2)^{1-δ}

, and

Ω(n/4^kk^2)^{1-δ}

, 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. (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

\neg f

The threshold degree of a Boolean function

f\colon\{0,1\}^n\to\{0,1\}

is the minimum degree of a real polynomial

p

that represents

f

in sign:

\mathrm{sgn}\; p(x)=(-1)^{f(x)}.

A related notion is sign-rank, defined for a Boolean matrix

F=[F_{ij}]

as the minimum rank of a real matrix

M

with

\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}

. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (

\text{AC}^{0}

) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications. We give an essentially optimal solution to this problem. For any

ε>0,

we construct an

\text{AC}^{0}

circuit in

n

variables that has threshold degree

Ω(n^{1-ε})

and sign-rank

\exp(Ω(n^{1-ε})),

improving on the previous best lower bounds of

Ω(\sqrt{n})

and

\exp(\tildeΩ(\sqrt{n}))

, respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of

\text{AC}^{0}

circuits of any given depth, with a strict improvement starting at depth

4

. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of

\text{AC}^{0}

, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of

\text{AC}^{0}