![]() |
![]() |
University of Birmingham > Talks@bham > Theoretical computer science seminar > Proof complexity of positive branching programs
![]() Proof complexity of positive branching programsAdd 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. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsSoCS PhD Research Training Sessions Applied Topology Colloquium Molecular and Medical Physics Seminar SeriesOther talksUltrafast Spectroscopy and Microscopy as probes of Energy Materials TBA Quantum Sensing in Space The tragic destiny of Mileva Marić Einstein Waveform modelling and the importance of multipole asymmetry in Gravitational Wave astronomy TBA |