UC Berkeley

What makes an algorithmic problem easy or hard? Many general algorithmic techniques arising from decades of research, along with the theory of NP-completeness based on reductions between hard problems, offers a good answer for problems where the input is ``worst-case''.

However, this theory has very little to say when the input is random, and comprises of independent samples, as is frequently the case for problems in statistics. Statistical problems seemingly go through abrupt phase transitions in complexity, from hard to easy once the number of samples crosses a threshold. Understanding this boundary between ``hard'' and ``easy'' for statistical problems is still in nascent stages.

This thesis comprises recent progress in understanding these phase transitions from the lens of semidefinite programming.