slideshow 3

Logic seminar

Propositional branching program proofs and logics for L and NL

Sam Buss
University of California, San Diego


Monday, 14. December 2020 - 15:30 to 17:00
Zoom meeting 472 648 284 - - contact to join
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.