BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1299
DTSTAMP:20230914T125958Z
SUMMARY:Lower bounds for Polynomial Calculus with extension variables over
finite fields
DESCRIPTION:Speaker: Sasank Mouli (University of California\, San Diego)\n\
nAbstract: \nPropositional proof complexity aims to prove lower bounds aga
inst tautological Boolean formulae for increasingly strong proof systems\,
with the ultimate goal of separating NP and coNP. A major open problem in
this area is lower bounds for AC0[p]-Frege proofs. Since lower bounds for
the corresponding circuit class AC0[p] were proved by Razborov and Smolen
sky through algebraic means\, algebraic proof systems such as Nullstellens
atz (Beame et. al.) and Polynomial Calculus (Clegg et. al.) were introduce
d with the intention of better understanding AC0[p]-Frege. Lower bounds fo
r the former systems have been obtained but it has not led to much progres
s for the latter. In this talk we will show how to obtain lower bounds for
a weak version of Polynomial Calculus with extension variables\, a proof
system which with strong enough extension variables can simulate AC0[p]-Fr
ege. In particular we show that for every prime p and n > 0\, there exist
tautologies over O(n log n) variables of degree O(log n) such that any Pol
ynomial Calculus proof with o(n^2) extension variables\, each depending on
O(log n) original variables requires exponential size. This builds on a r
ecent work of Sokolov (STOC 2020) and is joint work with Russell Impagliaz
zo and Toniann Pitassi\, appearing in CCC 2023.\n
URL:https://www.tcs.tifr.res.in/web/events/1299
DTSTART;TZID=Asia/Kolkata:20230605T160000
DTEND;TZID=Asia/Kolkata:20230605T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR