All reports by Author Ludmila Glinskih:

__
TR24-117
| 12th June 2024
__

Ludmila Glinskih, Artur Riazanov#### Partial Minimum Branching Program Size Problem is ETH-hard

__
TR19-020
| 4th February 2019
__

Ludmila Glinskih, Dmitry Itsykson#### On Tseitin formulas, read-once branching programs and treewidth

Revisions: 1

Ludmila Glinskih, Artur Riazanov

We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time. This result also applies to the partial minimization problems for many interesting subclasses of branching programs, such as read-$k$ branching programs and OBDDs.

Combining these results with our recent result (Glinskih ... more >>>

Ludmila Glinskih, Dmitry Itsykson

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 >>>