[Proof Complexity] Sam Buss' talk on Monday

thapen thapen at math.cas.cz
Sat Dec 12 18:00:51 CET 2020

Dear colleagues,

Sam Buss will give a proof complexity talk in our online logic seminar 
on Monday - see the announcement below.

To join go to
Passcode: 017107 (if required)




  Monday 14th December, 3:30pm

   Place: Zoom meeting 472 648 284 - https://cesnet.zoom.us/j/472648284


  Speaker:Sam Buss, University of California, San Diego
  Title: Propositional branching program proofs and logics for L and NL


  We introduce systems of propositional logic for reasoning directly with 
decision trees, non-deterministic decision trees, branching programs and 
non-deterministic branching programs. These propositional systems allow 
reasoning about properties in non-uniform logarithmic space and 
non-deterministic logarithmic space. We also report on work-in-progress 
to use these propositional proof systems for the bounded arithmetic 
theories VL and VNL with proof theoretic strength corresponding to 
logarithmic space and non-deterministic logarithmic space. The talk will 
start with an overview of the propositional proof systems which are 
already known to have close correspondences with bounded arithmetic. The 
new results are joint work with Anupam Das and Alexander Knop.

  For more information see the seminar web page at
  https://calendar.math.cas.cz/logic-seminar-actual .

Logic-seminar mailing list
Logic-seminar at math.cas.cz

More information about the Proof-Complexity mailing list