__
Revision #1 to TR18-197 | 26th November 2018 08:45
__
#### Approximate degree of AND via Fourier analysis

**Abstract:**
We give a new proof that the approximate degree of the AND function over $n$ inputs is $\Omega(\sqrt{n})$. Our proof extends to the notion of weighted degree, resolving a conjecture of Kamath and Vasudevan. As a consequence we reprove that the approximate degree of any read-once depth-2 De Morgan formula is the square root of the formula size up to constant. This generalizes a theorem of Sherstov (TOC 2013) and Bun and Thaler (Inf. Comput. 2015) and is a special case of a recent result of Ben-David et al. (FOCS 2018).

**Changes to previous version:**
Added an important reference and fixed an inaccuracy in Theorem 1.

__
TR18-197 | 22nd November 2018 06:28
__

#### Approximate degree of AND via Fourier analysis

**Abstract:**
We give a new proof that the approximate degree of the AND function over $n$ inputs is $\Omega(\sqrt{n})$. Our proof extends to the notion of weighted degree, resolving a conjecture of Kamath and Vasudevan. As a consequence we confirm that the approximate degree of any read-once depth-2 De Morgan formula is the square root of the formula size up to constant. This generalizes a result of Sherstov (TOC 2013) and Bun and Thaler (Inf. Comput. 2015).