BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1619
DTSTAMP:20250918T060656Z
SUMMARY:Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Qua
 dratic Depth
DESCRIPTION:Speaker: Sreejata Kishor  Bhattacharya (TIFR)\n\nAbstract: \n\n
 Itsykson and Sokolov [IS14] identified resolution over parities\, denote
 d by ResLin\, as a natural and simple fragment of AC0​[2]-Frege for wh
 ich no super-polynomial lower bounds on size of proofs are known. Building
  on a recent line of work\, Efremenko and Itsykson [EI25] proved lower b
 ounds of the form exp​(NΩ​(1))\, on the size of ResLin proofs whos
 e depth is upper bounded by O​(N​log⁡N)\, where N is the number o
 f variables of the unsatisfiable CNF formula. The hard formula they used w
 as Tseitin on an appropriately expanding graph\, lifted by a 2-stifling g
 adget. They posed the natural problem of proving super-polynomial lower bo
 unds on the size of proofs that are Ω​(N1+ϵ) deep\, for any constant
  ϵ>0.\nWe provide a significant improvement by proving a lower bound on 
 size of the form exp​(Ω~​(Nϵ))\, as long as the depth of the ResLi
 n proofs are O​(N2−ϵ)\, for every ϵ>0. Our hard formula is again 
 Tseitin on an expander graph\, albeit lifted with a different type of gadg
 et. Our gadget needs to have small correlation with all parities.\nAn impo
 rtant ingredient in our work is to show that arbitrary distributions lift
 ed with such gadgets fool safe affine spaces\, an idea which originates
  in the earlier work of Bhattacharya\, Chattopadhyay and Dvorak [BCD24].\
 nThis talk is based on joint work with Arkadev Chattopadhyay.\n
URL:https://www.tcs.tifr.res.in/web/events/1619
DTSTART;TZID=Asia/Kolkata:20250919T160000
DTEND;TZID=Asia/Kolkata:20250919T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR