ECCC-Report TR18-197https://eccc.weizmann.ac.il/report/2018/197Comments and Revisions published for TR18-197en-usMon, 26 Nov 2018 08:45:46 +0200
Revision 1
| Approximate degree of AND via Fourier analysis |
Andrej Bogdanov
https://eccc.weizmann.ac.il/report/2018/197#revision1We 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).
Mon, 26 Nov 2018 08:45:46 +0200https://eccc.weizmann.ac.il/report/2018/197#revision1
Paper TR18-197
| Approximate degree of AND via Fourier analysis |
Andrej Bogdanov
https://eccc.weizmann.ac.il/report/2018/197We 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).Thu, 22 Nov 2018 06:46:10 +0200https://eccc.weizmann.ac.il/report/2018/197