Unlocking the Power of Fine-Grained Complexity Theory: Insights from Manuel Sabin’s UC Berkeley Dissertation 🎓

This was my dissertation talk on April 20, 2020 given and recorded on Zoom. This finishes off my 6 year PhD at UC Berkeley in Theoretical Computer Science advised by Shafi Goldwasser and Christos Papadimitriou.

Title:
On The Utility of Fine-Grained Complexity Theory

Abstract:
Fine-Grained Complexity Theory has emerged rapidly in the past decade. By studying the "exact polynomial time complexity" of computational problems (e.g. solvable in n^2 vs n^3 time), this nascent field gives a better understanding of the practical difficulty of problems than the lens of classical (coarse-grained) Complexity Theory. With this problem-centric view, however, we lose many of the connections to the deep philosophical questions that classical Complexity Theory probes, such as

- Can we use computational hardness to hide secrets? (Cryptography)

- Is it as easy to verify a problem's solutions as it is to find them? (P vs NP)

- Can we find as many answers in a world where we didn't have access to randomness? (Derandomization)

- Can a problem that is hard in the worst-case scenario be turned into one that is hard almost always? (Hardness Amplification)

We show that connections to these philosophical problems can be recovered and that the problem-specific claims of Fine-Grained Complexity Theory cannot exist in a vacuum without ramifications to the structural resource-centric claims of classical Complexity Theory.