University of Birmingham > Talks@bham > Theoretical computer science seminar > Proof complexity of positive branching programs

Proof complexity of positive branching programs

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Anupam Das.

We investigate the proof complexity of systems based on positive branching programs. Positive NBPs compute monotone Boolean functions, just like negation-free circuits or formulas, but constitute a positive version of (non-uniform) NL, rather than polynomial time or NC1 , respectively.

Our system eLNDT+ is obtained by restricting the system eLNDT to a positive syntax, similarly to how the `monotone sequent calculus’ MLK is obtained from the usual sequent calculus LK by restricting to negation-free formulas.

Our main result is that eLNDT+ polynomially simulates eLNDT over positive sequents. Our proof method is inspired by a similar result for MLK by Atserias, Galesi and Pudlak, that was recently improved to a bona fide polynomial simulation via works of Jerabek and Buss, Kabanets, Kolokolova and Koucky.

This talk is based on joint work with Anupam Das: https://arxiv.org/abs/2102.06673 .

Zoom link: https://bham-ac-uk.zoom.us/j/4040590387?pwd=dlJpN0tyUVJQQWxyUzc3SisvcHJtUT09

This talk is part of the Theoretical computer science seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.