Back to search

Boston University

On characterizing optimal Boolean circuits and their applications

Abstract

dc:description.abstract

Determining 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 × 3

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en_US

Identifiers

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

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

Dang, Ngu. On characterizing optimal Boolean circuits and their applications. doctoral thesis, Boston University, 2026. https://hdl.handle.net/2144/53772