Departmental Colloquium
Dmitriy Kunisky
Yale University
The computational cost of detecting hidden structures: from random to deterministic
Abstract: I will present a line of work on the computational complexity of several algorithmic tasks on random inputs, including hypothesis testing, sampling, and "certification" for optimization problems (where an algorithm must output a bound on a problem's optimum rather than just a high-quality solution). Surprisingly, these diverse tasks admit a unified analysis involving the same two main ingredients. The first is the study of algorithms that output low-degree polynomial functions of their inputs. Such algorithms are believed to be optimal for many statistical tasks and can be understood with the theory of orthogonal polynomials, leading to strong evidence for the hardness of certain hypothesis testing problems. The second is a strategy of "planting" unusual structures in problem instances, which gives reductions from hypothesis testing to tasks like sampling and certification. I will focus on examples of the latter motivated by statistical physics: (1) sampling from Ising models, and (2) certifying bounds on the Hamiltonian of the Sherrington-Kirkpatrick spin glass model.
Next, by examining the sum-of-squares hierarchy of semidefinite programs, I will demonstrate how reasoning with planted solutions can show computational hardness of certification problems not only in random settings under strong distributional assumptions, but also for more generic problem instances. As an extreme example, I will show how some of the above ideas may be completely derandomized and applied in a deterministic setting. Using as a testbed the long-standing open problem in number theory and Ramsey theory of bounding the clique number of the Paley graph, I will give an analysis of semidefinite programming that suggests both new theoretical approaches to proving stronger bounds on the clique number and refined notions of pseudorandomness capturing deterministic versions of phenomena from random matrix theory.
Thursday January 11, 2024 at 3:00 PM in 636 SEO