UC San Diego

This dissertation presents several results in fine-grained complexity. Fine-grained complexity aims at extending traditional complexity theory by making more precise, and fine-grained, statements on the complexity of problems in various resources, including time and space. In doing so, fine-grained complexity distinguishes between false equivalences, such as the equivalence of all NP-complete problems, while also exploring the connections between traditionally separate realms, such as polynomial and exponential time.

This dissertation takes a fine-grained view on computational problems from a range of fields, including geometry, biology, computational complexity, economics and graph theory.

We study the relationship between the satisfiability problem on threshold circuits and a geometric problem, giving the first non-trivial algorithms for both. From economics, we study the stable matching problem, giving both upper and lower bounds on the problem. We also take a fine-grained view on the power of dynamic programming, again proving both upper and lower bound, as well as relating dynamic programming to other algorithmic paradigms in a fine-grained manner. Finally, we study the relationship between several problems central to the field of fine-grained complexity, including satisfiability, 3-sum and the all-pairs shortest path problem, giving the first fine-grained non-reducibility results.