BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1555
DTSTAMP:20250522T095346Z
SUMMARY:Cutting Planes and Monotone Feasible Interpolation
DESCRIPTION:Speaker: Sreejata Kishor  Bhattacharya (TIFR)\n\nAbstract: \nCu
 tting Planes is a proof system which certifies a system of linear inequali
 ties has no integer solution by repeatedly deriving new inequalities by li
 near combinations and rounding-up of previous inequalities. As a proof sys
 tem\, it is strictly stronger than resolution - and lower bounds for it ar
 e hard to prove. The only known technique is the Monotone Interpolation Pr
 operty\, which in turn uses lower bounds from monotone circuit complexity.
  However\, currently this technique can be used only for a very restrictiv
 e set of CNFs - it's not yet known if random constant-width CNFs are hard 
 for Cutting Planes. We shall describe the MIP technique and mention some o
 pen problems on which there has been exciting progress in the past few yea
 rs.\n \n
URL:https://www.tcs.tifr.res.in/web/events/1555
DTSTART;TZID=Asia/Kolkata:20250523T160000
DTEND;TZID=Asia/Kolkata:20250523T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR