#  Harvard Logic Colloquium: Sam Buss (UCSD) "Bounded Arithmetic, Expanders, and Monotone Propositional Proofs" 

 



####  calendar\_today Date and Time 

 **October 24, 2018** 

 03:00PM - 04:00PM EDT 

####  pin\_drop Location 

 **Logic Center, Room 420, 2 Arrow Street**  



 

 



 

This talk discusses a new combinatorial proof of the existence of expander graphs, which can be carried out in the bounded arithmetic theory VNC1 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.

 

 



 

 See also:- [ Harvard Logic Colloquium ](/department-events/harvard-logic-colloquium)
 
 

 Share on:- [     Facebook ](#)
- [     Twitter ](#)
- [     Linkedin ](#)
 


 Save: [ Add to calendar calendar\_today ](https://philosophy.fas.harvard.edu/node/1342461/event-feed.ics)  Copy link link