VP vs VNP and Bounded Depth Circuits
Event details
| Date | 02.06.2015 |
| Hour | 16:15 › 17:15 |
| Speaker | Ankit Gupta (EPFL) |
| Location |
INF 211
|
| Category | Miscellaneous |
In the algebraic version of P vs NP problem one has to show that there are no efficient algebraic algorithms for computing 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 permanent 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) translates to an exp(n^{\epsilon}) size lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent via circuits in the class C and show that any such circuit has exp(Ω(n^{1/2})) size.
We then extend the results of Agrawal-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})}.
Based on joint works with Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi.
We then extend the results of Agrawal-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})}.
Based on joint works with Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi.
Practical information
- Informed public
- Free
Organizer
- Nisheeth Vishnoi