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.2015.72
URN: urn:nbn:de:0030-drops-50491
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5049/
Go to the corresponding LIPIcs Volume Portal

Bhowmick, Abhishek ; Lovett, Shachar

Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds

pdf-format:
1.pdf (0.5 MB)

Abstract

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.

BibTeX - Entry

@InProceedings{bhowmick_et_al:LIPIcs:2015:5049,
  author =	{Abhishek Bhowmick and Shachar Lovett},
  title =	{{Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{72--87},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{David Zuckerman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5049},
  URN =		{urn:nbn:de:0030-drops-50491},
  doi =		{10.4230/LIPIcs.CCC.2015.72},
  annote =	{Keywords: nonclassical polynomials, polynomials, lower bounds, barrier}
}

Keywords: nonclassical polynomials, polynomials, lower bounds, barrier
Collection: 30th Conference on Computational Complexity (CCC 2015)
Issue Date: 2015
Date of publication: 06.06.2015

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