Algebraic Complexity Seminar

Exponential Lower Bounds for Depth-3 Algebraic Circuits over Constant-Sized Fields

We will discuss a result of Grigoriev-Karpinski and Grigoriev-Razborov that shows that any depth-3 algebraic circuit for the permanent or determinant when only using constants from a constant-sized finite field (such as F_2) must be a computation of size 2^\Omega(n). We will then discuss how obtaining such a bound when using unrestricted constants (over the complex numbers) would separate VP and VNP.