![Meta-complexity_logo_hi-res](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-02/Meta-complexity_hi-res.png.jpg?itok=oFqprXq1)
Abstract
In this talk I will 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 and Riazanov, LATIN 2022) we obtain an unconditional superpolynomial lower bound on the size of Read-Once Nondeterministic Branching Programs (1-NBP) computing the total versions of the minimum BP, read-k-BP, and OBDD size problems. Additionally we show that for any k > 2, it is NP-hard to check whether a given read-k-BP computing partial Boolean function can be compressed to a read-k-BP of linear size.
Based on joint work with Artur Riazanov.