Login
Talks & Seminars
Title: VP versus VNP and depth four lower bounds
Mr. Pritish Kamath, Microsoft Research India, Bangalore
Date & Time: November 8, 2012 15:00
Venue: Conference Room, 01st Floor, C Block, Dept. of Computer Science & Engineering, Kanwal Rekhi building
Abstract:
VP vs VNP conjecture (also known as Determinant vs. Permanent conjecture), the algebraic analog of P vs NP, has been a long standing open problem, ever since it was proposed by Leslie Valiant in 1979. Briefly stating, the conjecture says that there does not exist any polynomial sized arithmetic circuit computing the Permanent, as against the Determinant which is known to have polynomial sized arithmetic circuits. In the recent times, there have been a flurry of results proving lower bounds in certain special cases of arithmetic circuits and formulae, none of which however prove a super-polynomial lower bound in the most general case. Recently, Agrawal-Vinay [FOCS 2008] and Koiran [TCS 2012] have shown that “strong enough” lower bounds for depth four formulae will imply super-polynomial lower bounds for general arithmetic circuits! In this context, we have been able to show lower bounds for a certain class of depth four formulae computing the Permanent, which come surprisingly “close” to the barrier needed to separate VP from VNP! In this talk, I would first define the notion of arithmetic circuits/formulae and the complexity classes VP and VNP. I would then describe the depth-reduction results of Agrawal-Vinay and Koiran, following which I would demonstrate the new lower bound that we have shown. [Our results are available here: http://eccc.hpi-web.de/report/2012/098/] I would not assume any prior background in arithmetic complexity, so the talk should be accessible to everybody.
Speaker Profile:
Pritish Kamath graduated with a B. Tech. in Computer Science and Engineering from IIT Bombay in 2012. He was the recipient of the President of India Gold Medal from IIT Bombay. He is currently a member of the theoretical computer science research group at Microsoft Research India, Bangalore.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback