BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Theoretical computer science seminar
SUMMARY:Proof complexity of positive branching programs -
Avgerinos Delkos
DTSTART:20210625T130000Z
DTEND:20210625T140000Z
UID:TALK4601AT
URL:/talk/index/4601
DESCRIPTION:We investigate the proof complexity of systems bas
ed on positive branching programs. Positive NBPs c
ompute monotone Boolean functions\, just like nega
tion-free circuits or formulas\, but constitute a
positive version of (non-uniform) NL\, rather than
polynomial time or NC1\, respectively.\n\n\nOur s
ystem 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 ne
gation-free formulas.\n\nOur main result is that e
LNDT+ polynomially simulates eLNDT over positive s
equents. Our proof method is inspired by a similar
result for MLK by Atserias\, Galesi and Pudlak\,
that was recently improved to a bona fide polynomi
al simulation via works of Jerabek and Buss\, Kaba
nets\, Kolokolova and Koucky.\n\nThis talk is base
d on joint work with Anupam Das: https://arxiv.org
/abs/2102.06673 .\n\nZoom link: https://bham-ac-uk
.zoom.us/j/4040590387?pwd=dlJpN0tyUVJQQWxyUzc3Sisv
cHJtUT09\n
LOCATION:Via Zoom (see link in abstract)
CONTACT:Anupam Das
END:VEVENT
END:VCALENDAR