Abstract
dc:description.abstractWe 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.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Boston University
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Glinskih, Ludmila
- Advisors dc:contributor.advisor
-
- Bun, Mark
- Raskhodnikova, Sofya
- ORCID dc:identifier.orcid
Subjects
dc:subject × 1Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53086