Raghavendra and Steurer 2018 Held Prize
Raghavendra and Steurer have made revolutionary contributions to the understanding of optimization and complexity in computer science, work that has relevance for solving the most difficult and intractable of computing problems.
Their work — conducted both individually and often in collaboration — suggests that among all efficient algorithms, semidefinite programming gives the best possible approximation guarantees for a host of “hard” optimization problems involving, for example, constraint satisfaction or graph partitioning.
Raghavendra built upon Subhash Khot’s 2003 unique games conjecture (UGC) to show that a concrete algorithm based on the technique of semidefinite programming is optimal for every constraint satisfaction problem. Later, Raghavendra and Steurer developed the small set expansion hypothesis that yields an even greater array of algorithmic implications than those implied by the unique games conjecture. These works yield a potential characterization of the limits up to which efficient algorithms can approximate broad classes of NP-hard optimization problems. Subsequently, the awardees have advanced a theoretical framework for semidefinite programming, one that has led to new algorithms and a deeper understanding of the limitations of semidefinite programming.
The Michael and Sheila Held Prize, presented for the first time in 2018, will be presented annually and carries with it a $100,000 prize. The prize honors outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. The prize is intended to recognize recent work (defined as published within the last eight years). The prize was established in 2017 by the bequest of Michael and Sheila Held.
