[Proof Complexity] Sam Buss' talk on Monday

[thapen]

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
https://cesnet.zoom.us/j/472648284?pwd=ZTlxeHhqWlltR1AzZC9CTHgzZ2tRZz09
Passcode: 017107 (if required)

Best,

Neil

  
-------------------------------------------------------------------------

  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

  Abstract

  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
https://list.math.cas.cz/listinfo/logic-seminar