Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR18-197 | 26th November 2018 08:45

#### Approximate degree of AND via Fourier analysis

Revision #1
Authors: Andrej Bogdanov
Accepted on: 26th November 2018 08:45
Keywords:

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.

### Paper:

TR18-197 | 22nd November 2018 06:28

#### Approximate degree of AND via Fourier analysis

TR18-197
Authors: Andrej Bogdanov
Publication: 22nd November 2018 06:46
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).