Partial Minimum Branching Program Size Problem is ETH-hard

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