Proof complexity of positive branching programs

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

• Avgerinos Delkos
• Friday 25 June 2021, 14:00-15:00
• Via Zoom (see link in abstract).

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.

This talk is included in these lists:

• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Theoretical computer science seminar
• Via Zoom (see link in abstract)
• computer sience

Note that ex-directory lists are not shown.