Under the auspices of the Computational Complexity Foundation (CCF)

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