Events
Fall 2014
Algebraic Complexity Seminar
Friday, November 21st, 2014, 11:00 am–12:00 pm
Parent Program:
Speaker:
Klim Efremenko (Tel Aviv University)
Location:
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.