UW CSE professor James Lee has won a Best Paper Award at the 2015 ACM Symposium on Theory of Computing (STOC) for his recent breakthrough research with David Steurer of Cornell and UW CSE Ph.D. alum Prasad Raghavendra of Berkeley. Their paper shows that one of the most powerful techniques currently available for designing polynomial-time algorithms will not work for fundamental NP-complete problems such as the Traveling Salesman Problem, the Maximum Independent Set problem, and a number of other combinatorial problems.
In the award paper, James and his colleagues study the efficacy of convex programming relaxations, specifically those expressed as semidefinite programs (SDPs). SDPs can be seen as combining the rich expressiveness of linear programs with the global geometric power of spectral methods. For many problems, SDP-based algorithms are widely viewed as the strongest tool in the algorithm designer’s arsenal. This new result is a rare example where computer scientists can show formally that a powerful computational model cannot efficiently solve NP-complete problems. The paper draws on techniques and intuitions from many areas, including proof complexity, machine learning, and quantum information theory.
These results fit into a long line of James’ research exploring the rich interplay between computation and geometry, probability, and physics. Those connections are not limited to impossibility results. For instance, James’ work on spectral algorithms has the potential for impact in a variety of other areas including machine learning, data mining, scientific computing, and computer vision. See his web page for more details.
Congratulations James!