Name
Abstract | ||
|---|---|---|
We study the computational complexity of approximating the 2-to-q norm of linear operators (defined as |A|2-q = maxv≠ 0|Av|q/|v|2) for q 2, as well as connections between this question and issues arising in quantum information theory and the study of Khot's Unique Games Conjecture (UGC). We show the following: For any constant even integer q ≥ 4, a graph G is a small-set expander if and only if the projector into the span of the top eigenvectors of G's adjacency matrix has bounded 2-q norm. As a corollary, a good approximation to the 2-q norm will refute the Small-Set Expansion Conjecture --- a close variant of the UGC. We also show that such a good approximation can be obtained in exp(n2/q) time, thus obtaining a different proof of the known subexponential algorithm for Small-Set-Expansion. Constant rounds of the "Sum of Squares" semidefinite programing hierarchy certify an upper bound on the 2-4 norm of the projector to low degree polynomials over the Boolean cube, as well certify the unsatisfiability of the "noisy cube" and "short code" based instances of Unique-Games considered by prior works. This improves on the previous upper bound of exp(logO(1) n) rounds (for the "short code"), as well as separates the "Sum of Squares"/"Lasserre" hierarchy from weaker hierarchies that were known to require ω(1) rounds. We show reductions between computing the 2-4 norm and computing the injective tensor norm of a tensor, a problem with connections to quantum information theory. Three corollaries are: (i) the 2-4 norm is NP-hard to approximate to precision inverse-polynomial in the dimension, (ii) the 2-4 norm does not have a good approximation (in the sense above) unless 3-SAT can be solved in time exp(√n poly log(n)), and (iii) known algorithms for the quantum separability problem imply a non-trivial additive approximation for the 2-4 norm. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2213977.2214006 | symposium on the theory of computing |
Keywords | DocType | Volume |
Semidefinite programming,hypercontractive,injective tensor norm,unique games conjecture | Conference | abs/1205.4484 |
ISSN | Citations | PageRank |
Proc. STOC 2012, pp. 307--326 | 22 | 0.79 |
References | Authors | |
28 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boaz Barak | 1 | 2563 | 127.61 |
| Fernando G.S.L. Brandao | 2 | 151 | 14.90 |
| Aram W. Harrow | 3 | 346 | 34.38 |
| Jonathan Kelner | 4 | 654 | 35.91 |
| David Steurer | 5 | 934 | 44.91 |
| Yuan Zhou | 6 | 290 | 28.29 |