Output details
11 - Computer Science and Informatics
University College London
Hypercontractivity, Sum-of-Squares Proofs, and their Applications
<10>This paper, in collaboration with researchers at MIT and Microsoft Research, presents a new direction in the use of semidefinite programs for approximating optimization problems. We obtained the fastest known algorithm for computing hyper-contractive norms, an important problem in Monte-Carlo simulations; previous algorithms were exponential, and we achieve quasi-polynomial time (n^(log n)). We were invited to publish the full version of the paper in the special edition of SIAM Journal of Computing for the best papers of STOC’12. Several follow-up papers have since appeared in FOCS’12, SODA’13, STOC’13 continuing the line of investigation initiated in the paper