Title: Lower Bounds for Homogeneous Depth 4 Arithmetic Circuits
Speaker: Mrinal Kumar, Rutgers University
Date: Tuesday, April 1, 2014 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
In this talk, we will prove super-polynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. This result builds upon and extends a long line of recent works which prove super-polynomial (and in some cases exponential) lower bounds for various restricted classes of homogeneous depth 4 circuits. The interest in homogeneous depth 4 circuits is motivated by the 'depth reduction' results of Agrawal-Vinay, Koiran and Tavenas which show that strong enough lower bounds for homogeneous depth four circuits would suffice to answer the VP vs VNP question in algebraic complexity theory, which is an algebraic analogue of the more well known P vs NP question. Joint work with Shubhangi Saraf.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math