BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1686
DTSTAMP:20260225T044418Z
SUMMARY:On Propositional Reasoning with Parities
DESCRIPTION:Speaker: Dmitry Itsykson (Ben-Gurion University of the Negev)\n
 \nAbstract: \nIn the talk\, we consider the propositional proof system Res
 olution over Parities (Res(⊕))\, in which the unsatisfiability of a Bool
 ean formula is established by analyzing the parity of sums of variables\, 
 that is\, through case analysis. This proof system extends classical Resol
 ution by allowing reasoning modulo 2\, thereby providing a more expressive
  framework for capturing parity-based inference. Understanding the strengt
 hs and limitations of Res(⊕) is an important step toward clarifying the 
 role of parity in propositional proofs and SAT solving.A central open prob
 lem is to construct formulas that do not admit short (polynomial-size) ref
 utations in this system. For many years\, such hard instances were known o
 nly for the tree-like version of Res(⊕)\, which forbids the simultaneous
  analysis of multiple cases.In this talk\, I will provide an overview of r
 ecent progress beyond tree-like restrictions\, establishing exponential lo
 wer bounds for bounded-depth Res(⊕)\, where the depth grows superlinearl
 y. I will also highlight the main lower-bound techniques\, including rando
 m walks with restarts and lifting with stifling gadgets. No prior backgro
 und in proof complexity will be assumed.\nShort Bio: Dmitry Itsykson is a 
 non-faculty researcher at Ben-Gurion University of the Negev (BGU). He rec
 eived his PhD from St. Petersburg State University in 2009 and his Habilit
 ation in 2022 from the St. Petersburg Department of Steklov Mathematical I
 nstitute of the Russian Academy of Sciences (PDMI). He has been a member o
 f PDMI since 2009\, where he holds the rank of Leading Researcher\, and ha
 s been on leave since joining BGU in 2022.He held part-time Associate Prof
 essor positions at St. Petersburg Academic University (2010–2019) and St
 . Petersburg State University (2018–2022). His research interests are in
  computational complexity theory\, with a focus on propositional proof com
 plexity\, average-case complexity\, and lower bounds for Boolean satisfiab
 ility (SAT) algorithms.\n
URL:https://www.tcs.tifr.res.in/web/events/1686
DTSTART;TZID=Asia/Kolkata:20260225T160000
DTEND;TZID=Asia/Kolkata:20260225T170000
LOCATION:A -201
END:VEVENT
END:VCALENDAR