BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1400
DTSTAMP:20240222T081357Z
SUMMARY:Exponential Separation Between Powers of Regular and General Resolu
tion Over Parities
DESCRIPTION:Speaker: Sreejata Kishor Bhattacharya (TIFR)\n\nAbstract: \nPr
oving super-polynomial lower bounds on the size of proofs of unsatisfiabil
ity of Boolean formulas using resolution over parities\, is an outstanding
problem that has received a lot of attention after its introduction by Ra
z and Tzamaret. Very recently\, Efremenko\, Garlík and Itsykson proved th
e first exponential lower bounds on the size of ResLin proofs that were ad
ditionally restricted to be bottom-regular. We show that there are formul
as for which such regular ResLin proofs of unsatisfiability continue to ha
ve exponential size even though there exists short proofs of their unsatis
fiability in ordinary\, non-regular resolution. This is the first super-po
lynomial separation between the power of general ResLin and and that of re
gular ResLin for any natural notion of regularity. Our argument\, wh
ile building upon the work of Efremenko et al\, uses additional ideas from
the literature on lifting theorems.\nThis is joint work with Arkadev Cha
ttopadhyay and Pavel Dvorak.\n
URL:https://www.tcs.tifr.res.in/web/events/1400
DTSTART;TZID=Asia/Kolkata:20240223T143000
DTEND;TZID=Asia/Kolkata:20240223T153000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR