Abstract
dc:description.abstractDetermining the complexity of circuit minimization is a longstanding challenge. To clarify the landscape of minimal circuits, we ask: for a Boolean function $f$ and a complexity measure μ, can we characterize the μ-optimal circuits that compute $f$? For some (f, μ) pairs---e.g., $f$ is the $n$-bit $\OR$-function under μ being the DeMorgan size---the answer is straightforward. For other slightly more complicated choices---e.g., the $n$-bit $\XOR$-function under DeMorgan size counting NOT gates---such characterizations appear to hinge on deeper lower-bound techniques such as Gate Elimination. In this thesis, we first show that even when NOT gates are free, minimal circuits for \XORn (the $n$-bit $\XOR$-function) are ``shaped like'' binary trees of $(n - 1)$ \XOR2-subcircuits, matching Schnorr's classical $3(n-1)$ lower bound. Furthermore, we adapt our technique with optimal $\XOR$-circuits to also characterize optimal circuit structure for the equality testing function \EQn which outputs $1$ if two given binary strings of length $n$ are the same. Specifically, we show that optimal $\EQ$-circuits are also shaped like binary trees. We then show two applications for the characterization of optimal circuits. First, we exhibit an algorithm that produces counterexamples against circuits of size exactly $3(n-1)$ but \textbf{does not} compute \XORn. We call such algorithms as \emph{circuit checkers} which extends Blum and Kannan's line of work on \emph{program checkers} (Blum \& Kannan, 1995) to the Boolean circuits' regime. Designing circuit checkers for other explicit candidate functions can be of independent interest. Second, we develop connections of optimal circuit structures to meta-complexity, an area in complexity theory that investigates the resources required to evaluate or certify complexity properties (such as circuit size) of explicit objects. Focusing on Boolean circuit size and the Minimum Circuit Size Problem ($\MCSP$), we revisit Ilango's hardness for partial $\MCSP$ under the Exponential Time Hypothesis (ETH) (Ilango, 2020). The knowledge of optimal circuit structures is crucial to address the open question of extending Ilango's approach to total $\MCSP$. We discuss why neither \XORn nor \EQn are capable of achieving ETH-hardness of $\MCSP$ via this route which leads us to the Multiplexer ($\MUX$) as a potential candidate. Achieving a tight bound for $\MUX$ is a crucial step for proving ETH-hardness of $\MCSP$ via Ilango's approach. Thus, we improve its known lower bound of $2(n-1)$ (Paul, 1975) to $2n + \log n - o(1)$ and also show that our lower bound proof is also constructive (by exhibiting an efficient refuter) making this the first constructive improvement for $\MUX$'s lower bound in 50 years. We also analyze its best known upper-bound construction (Klein \& Patterson, 1980) to point out why $\MUX$ is a promising candidate for proving ETH-hardness of $\MCSP$.
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
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Dang, Ngu
- Advisor dc:contributor.advisor
-
- Homer, Steve
- ORCID dc:identifier.orcid
Subjects
dc:subject × 3Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53772