BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/753
DTSTAMP:20230914T125937Z
SUMMARY:How Limited Interaction Hinders Real Communication (and What it Mea
 ns for Proof and Circuit Complexity)
DESCRIPTION:Speaker: Marc Vinyals (KTH Royal Institute of Technology\nSchoo
 l of Computer Science and Communication\nLindstedtsvagen 5\nD Building\, 4
 518\nSweden)\n\nAbstract: \nNowadays SAT solvers are able to solve problem
 s with millions of variables\, but some instances are still hard. While so
 me formulas just require large time or memory to solve\, other formulas al
 low to trade these resources. In the language of proof complexity\, they h
 ave both short proofs and proofs in small space\, but optimizing either me
 asure blows up the other.\n\nIn this talk we will look at size-space trade
 -offs that hold not only for the resolution proof system\, which captures 
 most current solvers\, but for polynomial calculus and cutting planes\, wh
 ich capture algebraic and pseudo-boolean reasoning respectively. The proof
  goes through communication complexity\, and a key insight is to use a mod
 el of communication that captures short cutting planes proofs: communicati
 on with limited rounds and with real numbers (joint work with Susanna F. d
 e Rezende and Jakob Nordström).\n
URL:https://www.tcs.tifr.res.in/web/events/753
DTSTART;TZID=Asia/Kolkata:20170214T160000
DTEND;TZID=Asia/Kolkata:20170214T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR