An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Neeraj Kayal; Nutan Limaye; Chandan Saha; Srikanth Srinivasan

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Neeraj Kayal ,
Nutan Limaye ,
Chandan Saha ,
Srikanth Srinivasan

Foundations of Computer Science (FOCS) | October 2014

Published by IEEE - Institute of Electrical and Electronics Engineers

Invited to Special Issue of SICOMP journal

Download BibTex

We show here a N^sqrt(d) 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³ in our case) with 0,1-coefficients such that any homogeneous depth four arithmetic formula computing such an f must have size at least N^sqrt(d).

© IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.