Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

We show here a $2^{\Omega(\sqrt{d} \cdot \log N)}$ size lower bound for homogeneous depth four arithmetic formulas. That is, we give

an explicit family of polynomials of degree $d$ on $N$ variables (with $N = d^3$ in our case) with $0, 1$-coefficients such that

for any representation of ...
more >>>