Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-175 | 15th December 2014 20:58

Nonclassical polynomials as a barrier to polynomial lower bounds

RSS-Feed




TR14-175
Authors: Abhishek Bhowmick, Shachar Lovett
Publication: 16th December 2014 00:16
Downloads: 1536
Keywords: 


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 superlogarithmic 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.



ISSN 1433-8092 | Imprint