Boston University
Efficiently finding evidence in property testing and circuit complexity
Abstract
dc:description.abstractMany 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 × 1Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53581