Back to search

Boston University

Circuits and branching programs in meta-complexity

Abstract

dc:description.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.

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 × 1

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53086

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Glinskih, Ludmila. Circuits and branching programs in meta-complexity. doctoral thesis, Boston University, 2024. https://hdl.handle.net/2144/53086