{"id":{"repo_id":"bu","oai_identifier":"oai:open.bu.edu:2144/53772"},"canonical_url":"https://search.ndltd.org/etd/bu/oai:open.bu.edu:2144/53772","repository":{"repo_id":"bu","name":"Boston University","base_url":"https://open.bu.edu/oai/request"},"display":{"title":"On characterizing optimal Boolean circuits and their applications","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 $\\mu$, can we characterize the $\\mu$-optimal circuits that compute $f$? For some $(f, \\mu)$ pairs---e.g., $f$ is the $n$-bit $\\OR$-function under $\\mu$ 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 $\\XOR_n$ (the $n$-bit $\\XOR$-function) are ``shaped like'' binary trees of $(n - 1)$ $\\XOR_2$-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 $\\EQ_n$ 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 $\\XOR_n$. 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 $\\XOR_n$ nor $\\EQ_n$ 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$.","abstract_html":"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 <span class=\"etd-inline-math\">&mu;</span>, can we characterize the <span class=\"etd-inline-math\">&mu;</span>-optimal circuits that compute $f$? For some <span class=\"etd-inline-math\">(f, &mu;)</span> pairs---e.g., $f$ is the $n$-bit $\\OR$-function under <span class=\"etd-inline-math\">&mu;</span> 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 <span class=\"etd-inline-math\">\\XOR<sub>n</sub></span> (the $n$-bit $\\XOR$-function) are ``shaped like&#x27;&#x27; binary trees of $(n - 1)$ <span class=\"etd-inline-math\">\\XOR<sub>2</sub></span>-subcircuits, matching Schnorr&#x27;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 <span class=\"etd-inline-math\">\\EQ<sub>n</sub></span> 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 <span class=\"etd-inline-math\">\\XOR<sub>n</sub></span>. We call such algorithms as \\emph{circuit checkers} which extends Blum and Kannan&#x27;s line of work on \\emph{program checkers} (Blum \\&amp; Kannan, 1995) to the Boolean circuits&#x27; 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&#x27;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&#x27;s approach to total $\\MCSP$. We discuss why neither <span class=\"etd-inline-math\">\\XOR<sub>n</sub></span> nor <span class=\"etd-inline-math\">\\EQ<sub>n</sub></span> 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&#x27;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$&#x27;s lower bound in 50 years. We also analyze its best known upper-bound construction (Klein \\&amp; Patterson, 1980) to point out why $\\MUX$ is a promising candidate for proving ETH-hardness of $\\MCSP$.","abstract_has_math":true,"creators":["Dang, Ngu"],"institution":"Boston University","degree_name":"Doctor of Philosophy","degree_level":"doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Homer, Steve"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-18T20:13:58Z","subjects":["Computer science","Circuit complexity","Constructivity"],"languages":["en_US"],"rights":["Attribution 4.0 International"],"rights_urls":["http://creativecommons.org/licenses/by/4.0/"],"identifier_entries":[],"person_identifier_entries":[{"key":"dc:identifier.orcid","label":"ORCID","values":["0009-0004-2774-2247"],"render_values":[{"text":"0009-0004-2774-2247","href":"https://orcid.org/0009-0004-2774-2247","code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/2144/53772","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/2144/53772","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.bu.edu/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aopen.bu.edu%3A2144%2F53772","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Homer, Steve"]},{"key":"dc:creator","label":"Author","values":["Dang, Ngu"]},{"key":"dc:identifier.orcid","label":"ORCID","values":["0009-0004-2774-2247"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-10-22T18:20:15Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-10-22T18:20:15Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:date.updated","label":"Dc Date Updated","values":["2026-08-28T16:15:15Z"]},{"key":"dc:type","label":"Dc Type","values":["Thesis/Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Boston University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science","Circuit complexity","Constructivity"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2144/53772"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["2026"]},{"key":"dc:description.abstract","label":"Abstract","values":["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 $\\mu$, can we characterize the $\\mu$-optimal circuits that compute $f$? For some $(f, \\mu)$ pairs---e.g., $f$ is the $n$-bit $\\OR$-function under $\\mu$ 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 $\\XOR_n$ (the $n$-bit $\\XOR$-function) are ``shaped like'' binary trees of $(n - 1)$ $\\XOR_2$-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 $\\EQ_n$ 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 $\\XOR_n$. 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 $\\XOR_n$ nor $\\EQ_n$ 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$."]},{"key":"dc:title","label":"Title","values":["On characterizing optimal Boolean circuits and their applications"]}]}],"canonical_facts":{"dc:contributor.advisor":["Homer, Steve"],"dc:creator":["Dang, Ngu"],"dc:date.accessioned":["2026-10-22T18:20:15Z"],"dc:date.available":["2026-10-22T18:20:15Z"],"dc:date.issued":["2026"],"dc:date.updated":["2026-08-28T16:15:15Z"],"dc:description":["2026"],"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 $\\mu$, can we characterize the $\\mu$-optimal circuits that compute $f$? For some $(f, \\mu)$ pairs---e.g., $f$ is the $n$-bit $\\OR$-function under $\\mu$ 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 $\\XOR_n$ (the $n$-bit $\\XOR$-function) are ``shaped like'' binary trees of $(n - 1)$ $\\XOR_2$-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 $\\EQ_n$ 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 $\\XOR_n$. 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 $\\XOR_n$ nor $\\EQ_n$ 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$."],"dc:identifier.orcid":["0009-0004-2774-2247"],"dc:identifier.uri":["https://hdl.handle.net/2144/53772"],"dc:language.iso":["en_US"],"dc:rights":["Attribution 4.0 International"],"dc:rights.uri":["http://creativecommons.org/licenses/by/4.0/"],"dc:subject":["Computer science","Circuit complexity","Constructivity"],"dc:title":["On characterizing optimal Boolean circuits and their applications"],"dc:type":["Thesis/Dissertation"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Boston University"]},"updated_at":"2026-11-18T20:13:58Z"}