Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

We show that any depth-4 homogeneous arithmetic formula computing the Iterated Matrix Multiplication polynomial IMM n,d -- the (1, 1)-th entry of the product of d generic n × n matrices -- has size n Ω(log n ), if d = Ω (log 2 n ). More-over, any depth-4 homogeneous formula computing the determinant polynomial Det n -- the determinant of a generic n × n matrix -- has size n Ω(log n ) .

Authors

• Neeraj Kayal
• Nutan Limaye
• Chandan Saha 0001
• Srikanth Srinivasan 0001

Keywords

• arithmetic circuits
• lower bounds
• shifted partial derivatives