2026-07-23T05:17:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5049 2024-03-06T10:35:45Z ddc:004 open_access

Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds Bhowmick, Abhishek Lovett, Shachar nonclassical polynomials polynomials lower bounds barrier 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhishek Bhowmick and Shachar Lovett 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.72 urn:nbn:de:0030-drops-50491 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.72 eng https://creativecommons.org/licenses/by/3.0/legalcode