BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:VP vs VNP and Bounded Depth Circuits
DTSTART:20150602T161500
DTEND:20150602T171500
DTSTAMP:20260508T164323Z
UID:f7512f55992cb36dd582c5d2038f9315f2a9d4d150c9a1f5af5bb343
CATEGORIES:Miscellaneous
DESCRIPTION:Ankit Gupta (EPFL)\nIn the algebraic version of P vs NP proble
 m one has to show that there are no efficient algebraic algorithms for com
 puting the permanent of an n x n matrix of input variables. In other words
 \, we want to show that any arithmetic circuit computing the n x n permane
 nt polynomial has large size. Agrawal-Vinay'08 and Koiran'12 have recently
  shown that a strong enough size lower bound (exp(n^{1/2+\\epsilon})) for 
 a certain sub-class C of depth-4 circuits (computing the permanent) transl
 ates to an exp(n^{\\epsilon}) size lower bound for general arithmetic circ
 uits computing the permanent. Motivated by this\, we examine the complexit
 y of computing the permanent via circuits in the class C and show that any
  such circuit has exp(Ω(n^{1/2})) size.\nWe then extend the results of Ag
 rawal-Vinay'08 and Koiran'12 to depth-3 circuits (over Q). As a corollary\
 , this gives the first non-trivial depth-3 circuit for computing (over Q) 
 the determinant of an n x n matrix of variables and it has size n^{O(n^{1/
 2})}.\nBased on joint works with Pritish Kamath\, Neeraj Kayal\, Ramprasad
  Saptharishi.
LOCATION:INF 211
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR