Events
Fall 2014

Algebraic Complexity Seminar

Add to Calendar

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.