Back to search

Boston University

Efficiently finding evidence in property testing and circuit complexity

Abstract

dc:description.abstract

Many problems in theoretical computer science are naturally phrased as decision problems: does a given object have a property, can these constraints be satisfied, or does there exist a solution of a certain size? But a yes-or-no answer is often only the beginning. Even when a decision problem can be solved, we may also want concrete evidence that supports the answer: the specific part of the object that witnesses the property, an assignment satisfying the constraints, or a solution that achieves the desired bound. This dissertation studies when such evidence can be found efficiently. The first part of this dissertation considers property testing of context-free languages. Property testing is motivated by the challenge of working with big data: when an input is too large to be read in full, one tries to infer global properties from a small number of random queries. We study membership in context-free languages, where much of the prior work has focused on regular languages and Dyck-$m$ languages (well-balanced strings with $m$ types of parentheses). We introduce excursion languages---a natural generalization of the Dyck-1 language---in which symbols encode bounded steps of a walk. For every fixed choice of step bounds, we give an optimal tester whose number of queries is independent of the input length. As a consequence, we obtain an optimal tester for the Dyck-1 language, improving the previously best-known upper bound. The second part studies constructive circuit lower bounds. A circuit lower bound guarantees that every sufficiently small circuit fails somewhere. For a particular circuit, however, it does not say where such a failure occurs, and finding an error via brute force requires checking exponentially many inputs. We study whether gate elimination, a widely used technique for proving unrestricted circuit lower bounds for explicit functions, can be made constructive. We examine two such arguments and show how counterexamples can be extracted algorithmically. The third and final part concerns simple extensions of Boolean functions. When a Boolean function is extended by adding nondegenerate variables, its circuit complexity must increase by at least the number of variables added. We call the extension simple when this increase is exactly the number of additional variables. A minimum-size circuit computing the extension is therefore a natural witness to simplicity. Under structural assumptions on the optimal circuits for the original function, we give a fixed-parameter tractable algorithm that, on positive instances, finds such an optimal circuit.

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
  • Jackman, Timothy
Advisor dc:contributor.advisor
  • Homer, Steve
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/53581

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

Jackman, Timothy. Efficiently finding evidence in property testing and circuit complexity. doctoral thesis, Boston University, 2026. https://hdl.handle.net/2144/53581