![]() |
![]() |
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 listsdddd Filling in the blank – I will be ….... in 2050’ Jane LangdaleOther talksExtending the Lax type operator for finite W-algebras Sylow branching coefficients for symmetric groups Quantum simulations using ultra cold ytterbium Modelling uncertainty in image analysis. Geometry of alternating projections in metric spaces with bounded curvature Ultrafast, all-optical, and highly efficient imaging of molecular chirality |