BEGIN:VCALENDAR
VERSION:2.0
X-WR-CALNAME;VALUE=TEXT:Harvard Logic Colloquium: Sam Buss (UCSD) "Bounded Arithmetic, Expanders, and Monotone Propositional Proofs"
PRODID:-//Harvard events data//EN
BEGIN:VEVENT
UID:event_1342461_0
SUMMARY:Harvard Logic Colloquium: Sam Buss (UCSD) "Bounded Arithmetic, Expanders, and Monotone Propositional Proofs"
DESCRIPTION:This talk discusses a new combinatorial proof of the existence of expander graphs, which can be carried out in the bounded arithmetic theory VNC<sup>1</sup> corresponding to alternating linear time. As an application, we prove that the monotone propositional sequent calculus polynomially simulates the full propositional sequent calculus. Prior to this, only a quasipolynomial simulation was known. Joint work with Valentine Kabanets, Antonina Kolokolova, and Michal Koucky.
LOCATION:Logic Center, Room 420, 2 Arrow Street
STATUS:CONFIRMED
DTSTART:20181024T190000Z
DTEND:20181024T200000Z
END:VEVENT
END:VCALENDAR