UC Berkeley

This dissertation studies the computational complexity of various problems as a function of a real-valued parameter controlling the hardness. The motivating question behind all these problems is to precisely understand the value of this parameter where the problem transitions from computationally easy to computationally hard. Pursuing this goal often necessitates developing a deep understanding of both algorithmic and hardness techniques. We study such problems in two different contexts: approximation algorithms and average-case algorithms.In the first part of this dissertation, we study approximation algorithms for two problems: the permanent of positive semidefinite matrices and the EPR quantum Hamiltonian problem. Both these problems fall outside the scope of the standard hardness of approximation literature that targets NP problems. For both problems, we design improved approximation algorithms based on convex relaxations. For the permanent problem, we also prove the first exponential-factor hardness of approximation, showing that the easy-to-hard transition referenced above must occur at an exponentially large scale.In the second part, we study two types of problems with random inputs: hypothesis testing and certification. For hypothesis testing where the null hypothesis is a simple product distribution, we design a new recipe to argue that the low-degree likelihood ratio obtains optimal advantage among all polynomial-time tests. We instantiate this recipe for the planted clique problem, proving optimal hardness results that are tight up to arbitrarily small inverse polynomial errors. For certification, we study upper certificates for MAX-CUT and MAX-IND-SET in random $d$-regular graphs. We specifically focus on the less understood setting of small d (say 3 or 4), and we use computational techniques to prove new lower and upper bounds that are numerically nearly tight.