College of Engineering Seminars & Speakers

Back to Listing

Anamay Tengse "Natural proofs in the algebraic setting"

Event Type
Seminar/Symposium
Sponsor
Computer Science Theory Research Area
Location
3401 SC
Virtual
wifi event
Date
Sep 12, 2022   10:00 am  
Speaker
Anamay Tengse (U. Haifa)
Contact
Candice Steidinger
E-Mail
steidin2@illinois.edu
Phone
217-300-8564
Views
85
Originating Calendar
Computer Science Speakers Calendar

Abstract: 

Razborov and Rudich (1997) defined the framework of 'natural proofs', which captures several known techniques for proving lower bounds against booleans circuit classes. Their work further shows that a 'natural proof' cannot prove a superpolynomial lower bound against general boolean circuits, if sufficiently strong One Way Functions exist.

About two decades later in two independent works, Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), formulated an algebraic analogue for natural proofs. The work of Forbes, Shpilka and Volk further provides some evidence for a 'natural-proofs-barrier', similar to that in the boolean setting.

Through recent works with Chatterjee, Kumar, Ramya and Saptharishi, we have been able to shed some more light on algebraic natural proofs. In the talk, we will first formalise the notion of algebraic natural proofs, and then understand the key results in all the related works mentioned above. The rest of the talk will be a discussion aimed at understanding all these results in the larger context of proving lower bounds.

 

link for robots only