Date Posted: 4/09/2015

David Steurer and his coauthors have won one of the three best paper awards at the STOC 2015, the 47th Annual Symposium on the Theory of Computing.

The paper is entitled, "Lower bounds on the size of semidefinite programming relaxations", written together with James R. Lee (University of Washington) and Prasad Raghavendra (UC Berkeley).  Among the many consequences of their results is that no family of polynomial-size semidefinite programming relaxations can achieve better than a 7/8-approximation for MAX 3 SAT.