Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FLOW FORMULAS:
Reports tagged with flow formulas:
TR21-028 | 27th February 2021
Anastasia Sofronova, Dmitry Sokolov

Branching Programs with Bounded Repetitions and $\mathrm{Flow}$ Formulas

Restricted branching programs capture various complexity measures like space in Turing machines or length of proofs in proof systems. In this paper, we focus on the application in the proof complexity that was discovered by Lovasz et al. '95 who showed the equivalence between regular Resolution and read-once branching programs ... more >>>




ISSN 1433-8092 | Imprint