License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.15
URN: urn:nbn:de:0030-drops-75258
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7525/
Go to the corresponding LIPIcs Volume Portal

Tal, Avishay

Tight Bounds on the Fourier Spectrum of AC0

pdf-format:
LIPIcs-CCC-2017-15.pdf (0.7 MB)

Abstract

We show that AC^0 circuits on n variables with depth d and size m have at most 2^{-Omega(k/log^{d-1} m)} of their Fourier mass at level k or above. Our proof builds on a previous result by Hastad (SICOMP, 2014) who proved this bound for the special case k=n. Our result improves the seminal result of Linial, Mansour and Nisan (JACM, 1993) and is tight up to the constants hidden in the Omega notation.

As an application, we improve Braverman's celebrated result (JACM, 2010). Braverman showed that any r(m,d,epsilon)-wise independent distribution epsilon-fools AC^0 circuits of size m and depth d, for r(m,d,epsilon) = O(log(m/epsilon))^{2d^2+7d+3}. Our improved bounds on the Fourier tails of AC^0 circuits allows us to improve this estimate to r(m,d,epsilon) = O(log(m/epsilon))^{3d+3}. In contrast, an example by Mansour (appearing in Luby and Velickovic's paper - Algorithmica, 1996) shows that there is a log^{d-1}(m)\log(1/epsilon)-wise independent distribution that does not epsilon-fool AC^0 circuits of size m and depth d. Hence, our result is tight up to the factor $3$ in the exponent.

BibTeX - Entry

@InProceedings{tal:LIPIcs:2017:7525,
  author =	{Avishay Tal},
  title =	{{Tight Bounds on the Fourier Spectrum of AC0}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{15:1--15:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{Ryan O'Donnell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7525},
  URN =		{urn:nbn:de:0030-drops-75258},
  doi =		{10.4230/LIPIcs.CCC.2017.15},
  annote =	{Keywords: bounded depth circuits, Fourier analysis, k-wise independence, Boolean circuits, switching lemma}
}

Keywords: bounded depth circuits, Fourier analysis, k-wise independence, Boolean circuits, switching lemma
Collection: 32nd Computational Complexity Conference (CCC 2017)
Issue Date: 2017
Date of publication: 01.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI