Partial Minimum Branching Program Size Problem is ETH-hard
<|reference_start|>Partial Minimum Branching Program Size Problem is ETH-hard: 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 the recent unconditional lower bounds for MCSP [Glinskih, Riazanov'22], 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 it is NP-hard to check whether a given BP computing a partial Boolean function can be compressed to a BP of a given size.<|reference_end|>
@article{glinskih2024partial,
    title={Partial Minimum Branching Program Size Problem is ETH-hard},
    author={Ludmila Glinskih and Artur Riazanov},
    journal={arXiv preprint arXiv:2407.04632},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04632},
    primaryClass={cs.CC}
}