BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1108
DTSTAMP:20230914T125950Z
SUMMARY:Algebraic Natural Proofs: the plot thickens
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nIn the late 1990s\, a pap
er by Razborov and Rudich pointed out a barrier towards proving boolean ci
rcuit lower bounds. They observed that almost all of the then known lower
bounds could be proved using a specific template: the 'natural proofs fram
ework'. They further showed that any 'natural proof' for P/poly (poly-size
d boolean circuits) would contradict the existence of One-Way-Functions: a
crucial primitive in modern day cryptography. Thus\, their paper essentia
lly ruled out "natural" techniques for proving strong boolean circuit lowe
r bounds.\n\nAbout two decades later\, two groups: Grochow\, Kumar\, Saks
and Saraf (2017)\, and Forbes\, Shpilka and Volk (2018)\, independently pr
oposed the framework of 'algebraically natural proofs' for algebraic circu
its. They observed that most of the known lower bounds against algebraic c
ircuit models fit in this framework\, and showed that 'algebraically natur
al proofs' do not exist for VP (poly-sized algebraic circuits)\, under a (
non-standard) derandomisation assumption. Forbes\, Shpilka and Volk (2018)
also provided some evidence that suggested that the derandomisation assum
ption might indeed be true.\n\nThis year\, in joint works with Chatterjee\
, Kumar\, Ramya and Saptharishi\, we observed the following seemingly cont
radictory facts about algebraically natural proofs.\n1. Algebraically natu
ral proofs (kind of) *exist* for all "interesting" polynomials in VP and V
NP (algebraic P and NP).\n2. Algebraically natural proofs *do not exist* f
or VNP (algebraic NP)\, if permanent is exponentially hard.\nIn this talk\
, we will first understand the algebraically natural proofs framework\, an
d then try to make sense of our recent findings.\n\nZoom link: https://zoo
m.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1108
DTSTART;TZID=Asia/Kolkata:20210101T171500
DTEND;TZID=Asia/Kolkata:20210101T181500
END:VEVENT
END:VCALENDAR