  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.
