An m-variate polynomial f is said to be an affine projection of some n-variate polynomial g if there exists an n \times m matrix A and an n-dimensional vector b such that f(x) = g(A x + b). In other words, if f can be obtained by replacing each variable ... more >>>
Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field \mathbb{F} of characteristic zero. We resolve this problem by proving a N^{\Omega(\frac{d}{\tau})} lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>>