Members' Colloquium

Any non-negative univariate polynomial over the reals can be written as a sum of squares.  This gives a simple-to-verify certificate of non-negativity of the polynomial. Rooted in Hilbert's 17th problem, there's now more than a century's work that finds the right multivariate generalizations called Positivstellensatz theorems (due to Krivine, Stengle, and Putinar). Beginning in the late 1980s, researchers (initially independent) in optimization, quantum information, and proof complexity theory found an algorithmic counterpart, the sum-of-squares algorithm, of these results. Over the past decade, this algorithmic theory has matured into a powerful tool for designing efficient algorithms for basic problems in algorithm design.

In this talk, I will outline a couple of highlights from these recent

developments:

1) Algorithmic Robust Statistics: In the 1960s, Tukey and Huber observed that most statistical estimators are brittle -- they break down with almost no guarantee if the model postulated for data has minor misspecification (say because of 1% outliers). In response, they initiated the field of robust statistics. Over the past five years, a new blueprint, based on the sum-of-squares algorithm, has emerged for efficient robust statistics in high dimensions with new connections to finding efficiently verifiable certificates of concentration and anti-concentration properties of high dimensional probability distributions.

2) The Kikuchi Matrix Method: Finding (or proving that there is none) a solution that satisfies 99% of a given system of k-sparse linear equations (i.e., k non-zero coefficients in each equation) over finite fields is a basic NP-hard problem and thus, unlikely to admit efficient algorithms. In the early 2000s, motivated by whether the hard instances are "pathological", researchers explored whether "semirandom" equations

-- arbitrary systems with right-hand sides generated uniformly and independently at random -- could admit efficient algorithms that output efficiently verifiable certificates of unsatisfiability. Recently, a restricted class of sum-of-squares proofs was at the heart of efficient algorithms for such semirandom sparse linear equations. Surprisingly, these algorithms have led to new progress in extremal combinatorics and coding theory.