A problem from theoretical computer science posed by Buhrman
asks to show that a certain class of circuits (NC0[+]) is bad at
decoding error correcting codes under random noise. (This would be
in contrast with an analogous class of quantum circuits...
We will discuss some results on high-degree varieties designed
to expand the reach of the polynomial method and explain their
applications in incidence geometry.
Irreducibility of random polynomials of large degree has been
studied recently in works by several authors (in particular by
Bary-Soroker, Kozma, Koukoulopoulos and by Varju and myself). We
study analogous problems in the setting of word maps in...