Pre-2018 CSE ID: CS2001-0686

This dissertation studies the fine-grained complexity of model checking problems for fixed logical formulas on sparse input structures.

The Orthogonal Vectors problem is an important and well-studied problem in fine-grained complexity: its hardness is implied by the Strong Exponential Time Hypothesis, and its hardness implies the hardness of many other interesting problems. We show that the Orthogonal Vectors problem is complete in the class of first-order model checking on sparse structures, under fine-grained reductions. In other words, the hardness of Orthogonal Vectors and the hardness of first-order model checking imply each other. This also gives us an improved algorithm for first-order model checking problems.

Among all first-order logic formulas in prenex normal form, we have reasons to believe that quantifier structures $\exists \dots \exists \forall$ and $\forall \dots \forall \exists$ may be the hardest in computational complexity: If the Nondeterministic version of the Strong Exponential Time Hypothesis is true, formulas of these forms are the only hard ones under the Strong Exponential Time Hypothesis.

We can add extensions to first-order logic to strengthen its expressive power. This work also studies the fine-grained complexity of first-order formulas with comparison on structures with total order, first-order formulas with transitive closure operations, first-order formulas of fixed quantifier rank, and first-order formulas of fixed variable complexity.

We also introduce a technique that can be used to reduce from sequential problems on graphs to parallel problems on sets, which can be applied to extending the Least Weight Subsequence problems from linear structures to some special classes of graphs.

Local search heuristics provide generalized ways of solving difficult computational problems. In this research we examine a few simple heuristics applied to the Planted Clique Problem, a problem for which there are a number of lower bounds for sophisticated algorithmic techniques. The heuristics run were able to solve the problem at a well known threshold, providing support for the efficacy of simple heuristics.

Proving circuit lower bounds is one of the most difficult tasks in computational complexity theory. The NP vs. P/poly problem asks whether there are small non-uniform circuits that can simulate circuit satisfiability. The answer is widely believed to be false, but so far progress has only been made in the case of restricted circuits. In the 1980s the progress stalled after it was shown that NP doesn’t have non-uniform AC0 circuits that have MOD-m gates for any prime m. After almost three decades, in the 2010s Williams made progress in the relaxed case of NEXP lower bounds. He first showed that non-trivial satisfiability algorithms for a circuit class entail NEXP lower bounds against that class. Then he designed a fast satisfiability algorithm for ACC circuits (AC0 circuits with MOD-m gates for any constant m) to show that NEXP doesn’t have non-uniform ACC circuits.

We make progress in bringing down the class NEXP, specifically by limiting non-determinism (in terms of the number of non-deterministic branches that accept). We show that slightly faster satisfiability algorithms entail lower bounds for UEXP and related classes. We believe this is progress towards making similar connections, and thus proving lower bounds, for EXP and lower complexity classes.

To investigate why progress again stalled around ACC lower bounds, and why TC0 (AC0 circuits with majority gates) lower bounds have not been established yet, Williams made rigorous connections between NEXP lower bounds and variations of Natural Proofs. Razborov and Rudich defined Natural Proofs to showcase the limitations of the current lower bound techniques. They showed that any technique that entails Natural Proofs, i.e. Proofs that are (i) constructive, (ii) useful, and (iii) large, fail to prove strong lower bounds. Williams showed that NEXP lower bounds, regardless of the technique, entail Proofs that satisfy the first two of the three conditions of Natural Proofs.

We make Williams connections more rigorous, and show that UEXP lower bounds entail Proofs, that in addition to the first two conditions of Natural Proofs, satisfy a third condition that is exactly the opposite of largeness condition. We call this condition, the uniqueness condition, and these Proofs, the Unique Proofs. These connections showcase that NEXP -> UEXP -> EXP is a viable path to approach EXP lower bounds.

We also discuss an alternate approach to improve NEXP lower bounds. We define a new form of non-determinism to capture the non-uniform circuits from the class (NP \cap coNP)/poly, and call it promise-Single-Valued non-determinism. We show that in the current NEXP lower bounds, we can allow the non-uniform circuits some limited non-determinism (in terms of the number of non-deterministic inputs) of the type promise-Single-Valued. We also discuss how small improvements in the amount of this special type of non-determinism, even in the restricted circuits much weaker than ACC, would imply very strong lower bounds such as NEXP not in P/poly.

This thesis will be a survey aimed to be an overview of some connections betweenrandomness extractors and pseudorandom generators in complexity theory. Particularly there will be a focus on how such connections are leveraged in achieving faster derandomization and “beating the hybrid argument”. We will cover both some classic results and examples, as well as some more recent ones

Reproducibility and replicability are central to the process of learning. Machine learning algorithms can solve a variety of tasks, in turn allowing researchers to ask new questions. However, reproducibility issues can limit the scope and utility of these algorithms. In this dissertation, we investigate replicability from a theoretical perspective. We formalize a new mathematical definition of replicability. Our definition applies to randomized algorithms that learn from independent and identically distributed (i.i.d.) samples. We propose replicable algorithms for fundamental learning tasks such as computing statistical queries, boosting weak learners, and learning halfspaces. We discuss techniques for designing replicable algorithms, resolving tensions among accuracy, replicability, and efficiency. Furthermore, we construct black-box algorithmic reductions between replicability and other notions of algorithmic stability, such as differential privacy. We also note possible directions for future replicability research.

• The introduction is a general-audience explanation of the contents of this dissertation.• In Chapter 1, we formally introduce replicability, the central concept of this dissertation. We mathematically define replicability and the associated model, noting key features and limitations. This chapter summarizes the theorems and algorithms in the remaining chapters. We mention promising future directions and argue why researchers should pursue them. • In Chapter 2, we list central definitions and briefly note how they are used. The remaining three chapters are reprints of three published conference papers related to replicable learning algorithms, with readability edits. • In Chapter 3, we mathematically define replicability and motivate our definition. We design new replicable algorithms for fundamental learning tasks such as computing statistical queries and learning halfspaces. This chapter discusses basic properties of replicability, including alternate definitions. • In Chapter 4, we exhibit a paper that predates and greatly contributed to this dissertation’s work on replicability. • In Chapter 5, we prove strong connections between replicability and other well-studied stability notions such as differential privacy. We show black-box ways to transform certain stable algorithms to replicable algorithms and vice versa. These transformations may increase the required sample sizes and run times. We prove these increases are necessary. Applications of our connections include new replicable learning algorithms and resolving open questions in algorithmic stability.

This dissertation presents several results at the intersection of

complexity theory and algorithm design. Complexity theory aims to

lower-bound the amount of computational resources (such as time and

space) required to solve interesting problems. Algorithm design aims

to upper-bound the amount of computational resources required to solve

interesting problems. These pursuits appear opposed. However, some

algorithm design and complexity lower bound problems are inextricably

connected.

This dissertation explores several such connections. From "natural"

proofs of circuit-size lower bounds, we create learning

algorithms. From the exact hardness of problems in polynomial time, we

create algorithms of estimating the acceptance probability of

circuits. Finally, from algorithms for testing the identity of

airthmetic circuits over finite fields, we create arithmetic

circuit-complexity lower bounds.

A critical challenge in complexity theory is establishing lower bounds on the size, depth, and complexity of Boolean circuits that compute explicit functions. General Boolean circuits, however, have proven resistant to such lower bounds. Consequently, the community has focused on proving lower bounds for more restricted families of circuits, such as bounded-depth circuits over various bases. A notable success in this area is the use of random restrictions, a method where input variables are fixed according to a probability distribution to simplify the circuit. This thesis explores the application of random restriction techniques to circuits and is structured to provide a thorough understanding of how random restrictions can also bee modified and refined to prove more general results.

We prove a new switching lemma that works for restrictions that set only a small fraction of the variables and is applicable to formulas in disjunctive normal form (DNFs) with small terms. We use this to prove lower bounds for the Res(k) propositional proof system, an extension of resolution which works with k-DNFs instead of clauses. We also obtain an exponential separation between depth d circuits of bottom fan-in k and depth d circuits of bottom fan-in k+1. Our results for Res(k) are as follows: 1. The 2n to n weak pigeonhole principle requires exponential size to refute in Res(k) for krootlog n/log log n. 2. For each constant k, there exists a constant w>k so that random w-CNFs require exponential size to refute in Res(k). 3. For each constant k, there are sets of clauses which have polynomial size Res(k+1) refutations but which require exponential size Res(k) refutations.