BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1505
DTSTAMP:20250102T063254Z
SUMMARY:Polynomial Calculus sizes over the Boolean and Fourier basis are in
 comparable
DESCRIPTION:Speaker: Sasank Mouli (IIT Indore)\n\nAbstract: \nFor every n >
  0\, we show the existence of a CNF tautology over O(n^2) variables of wid
 th O(log n) such that it has a Polynomial Calculus Resolution refutation o
 ver {0\, 1} variables of size O(n^3polylog(n)) but any Polynomial Calculus
  refutation over {+1\, −1} variables requires size 2^Ω(n). This shows t
 hat Polynomial Calculus sizes over the {0\, 1} and {+1\, −1} bases are i
 ncomparable (since Tseitin tautologies show a separation in the other dir
 ection) and answers an open problem posed by Sokolov [Sok20] and Razborov.
 \n \nShort Bio: Sasank Mouli is an Assistant Professor at IIT Indore. He 
 completed his PhD at UC San Diego under the guidance of Russell Impagliazz
 o. He was briefly a postdoc at IDSIA\, Lugano\, Switzerland. \n
URL:https://www.tcs.tifr.res.in/web/events/1505
DTSTART;TZID=Asia/Kolkata:20250121T160000
DTEND;TZID=Asia/Kolkata:20250121T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR