Arithmetic circuit lower bounds from sumset expansion

Anand Kumar Narayanan

Raz proposed a program to prove arithmetic circuit lower bounds through the explicit construction of elusive functions. These are polynomial maps from a low dimensional space to a…