Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Approximate degree of AND via Fourier analysis

RSS-Feed




Revision #1
Authors: Andrej Bogdanov
Accepted on: 26th November 2018 08:45
Downloads: 67
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
Downloads: 169
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 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).



ISSN 1433-8092 | Imprint