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