Output details
11 - Computer Science and Informatics
University College London
Return to search
Output 0 of 0 in the submission
Output title
Hypercontractivity, Sum-of-Squares Proofs, and their Applications
Type
E - Conference contribution
Name of conference/published proceedings
Proceedings of the 44th symposium on Theory of Computing
Volume number
-
Issue number
-
First page of article
307
ISSN of proceedings
-
Year of publication
2012
URL
-
Number of additional authors
6
Additional information
<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
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
7
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
