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.APPROX-RANDOM.2016.32
URN: urn:nbn:de:0030-drops-66550
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6655/
Go to the corresponding LIPIcs Volume Portal

Harsha, Prahladh ; Srinivasan, Srikanth

On Polynomial Approximations to AC^0

pdf-format:
LIPIcs-APPROX-RANDOM-2016-32.pdf (0.6 MB)

Abstract

We make progress on some questions related to polynomial approximations of AC^0. It is known, from the works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. 6th CCC 1991), that any AC^0 circuit of size s and depth d has an epsilon-error probabilistic polynomial over the reals of degree (log (s/epsilon))^{O(d)}. We improve this upper bound to (log s)^{O(d)}* log(1/epsilon), which is much better for small values of epsilon.

We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that (log s)^{O(d)}* log(1/epsilon)-wise independence fools AC^0, improving on Tal's strengthening of Braverman's theorem (J. ACM 2010) that (log (s/epsilon))^{O(d)}-wise independence fools AC^0. Up to the constant implicit in the O(d), our result is tight. As far as we know, this is the first PRG construction for AC^0 that achieves optimal dependence on the error epsilon.

We also prove lower bounds on the best polynomial approximations to AC^0. We show that any polynomial approximating the OR function on n bits to a small constant error must have degree at least ~Omega(sqrt{log n}). This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).

BibTeX - Entry

@InProceedings{harsha_et_al:LIPIcs:2016:6655,
  author =	{Prahladh Harsha and Srikanth Srinivasan},
  title =	{{On Polynomial Approximations to AC^0}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6655},
  URN =		{urn:nbn:de:0030-drops-66550},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.32},
  annote =	{Keywords: Constant-depth Boolean circuits, Polynomials over reals, pseudo-random generators, k-wise independence}
}

Keywords: Constant-depth Boolean circuits, Polynomials over reals, pseudo-random generators, k-wise independence
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

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