Circuits and branching programs in meta-complexity
OA Version
Citation
Abstract
We study complexity of representing various meta-complexity functions via circuits and branching programs, and connections between them. Studying such connections improves the understanding of structural complexity. * We show that it is unconditionally hard to decide a meta-complexity problem called the Minimum Circuit Size Problem (MCSP) via a read-once nondeterministic branching program.* We study hardness of minimizing a representation of a partial Boolean function as a branching program. We show that the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time for multiple types of deterministic branching programs assuming the Exponential Time Hypothesis (ETH) holds.
* We study how fixed polynomial circuit lower bounds may lead to new results in structural complexity. We show a new conditional collapse from studying circuit complexity of polynomial time randomized computations with one-sided error.
Description
2024