Fall 2014

Algebraic Complexity Seminar

Nov. 21, 2014 11:00 am12:00 pm

Add to Calendar


Klim Efremenko (Tel Aviv University)


Calvin Lab 116

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.