Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with read-once branching program:
TR98-018 | 27th March 1998
Martin Sauerhoff

Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs

Comments: 1

We extend the tools for proving lower bounds for randomized branching
programs by presenting a new technique for the read-once case which is
applicable to a large class of functions. This technique fills the gap
between simple methods only applicable for OBDDs and the well-known
"rectangle technique" of Borodin, Razborov ... more >>>

TR19-020 | 4th February 2019
Ludmila Glinskih, Dmitry Itsykson

On Tseitin formulas, read-once branching programs and treewidth

Revisions: 1

We show that any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on an $n\times n$ grid graph has size at least $2^{\Omega(n)}$. Then using the Excluded Grid Theorem by Robertson and Seymour we show that for arbitrary graph $G(V,E)$ any nondeterministic read-once branching program that computes ... more >>>

TR19-178 | 5th December 2019
Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

We show that the size of any regular resolution refutation of Tseitin formula $T(G,c)$ based on a graph $G$ is at least $2^{\Omega(tw(G)/\log n)}$, where $n$ is the number of vertices in $G$ and $tw(G)$ is the treewidth of $G$. For constant degree graphs there is known upper bound $2^{O(tw(G))}$ ... more >>>

ISSN 1433-8092 | Imprint