Hypercontractivity, sum-of-squares proofs, and their applications

DOI10.1145/2213977.2214006zbMath1286.68176arXiv1205.4484OpenAlexW2028932986WikidataQ59711931 ScholiaQ59711931MaRDI QIDQ5415483

David Steurer, Yuan Zhou, Jonathan A. Kelner, Boaz Barak, Aram W. Harrow, Fernando G. S. L. Brandão

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.4484

zbMATH Keywords

computational complexitysemidefinite programmingquantum information theoryunique games conjecturehypercontractiveinjective tensor normapproximation of the 2-to-\(q\) norm of linear operators

Mathematics Subject Classification ID

Semidefinite programming (90C22) Norms (inequalities, more than one norm, etc.) of linear operators (47A30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coding theorems (Shannon theory) (94A24) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Related Items (39)

Quantum de Finetti theorems under local measurements with applications ⋮ Narrow Proofs May Be Maximally Long ⋮ Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Making the Long Code Shorter ⋮ Noisy tensor completion via the sum-of-squares hierarchy ⋮ Semidefinite programming hierarchies for constrained bilinear optimization ⋮ Tight size-degree bounds for sums-of-squares proofs ⋮ A note on the Hausdorff distance between norm balls and their linear maps ⋮ Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization ⋮ Unnamed Item ⋮ Optimizing mean field spin glasses with external field ⋮ Approximate orthogonality of permutation operators, with application to quantum information ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Unnamed Item ⋮ Hypercontractivity via tensor calculus ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Certifying Unstability of Switched Systems Using Sum of Squares Programming ⋮ Hypercontractivity for semigroups of unital qubit channels ⋮ Limitations of semidefinite programs for separable states and entangled games ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ The sum-of-squares hierarchy on the sphere and applications in quantum information theory ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ An improved semidefinite programming hierarchy for testing entanglement ⋮ Hypercontractivity in finite-dimensional matrix algebras ⋮ Unnamed Item ⋮ Lift-and-project methods for set cover and knapsack ⋮ The global convergence of the nonlinear power method for mixed-subordinate matrix norms ⋮ Generic properties and a criterion of an operator norm ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Sum of squares bounds for the ordering principle ⋮ Optimization of mean-field spin glasses ⋮ Moments Tensors, Hilbert's Identity, and k-wise Uncorrelated Random Variables

This page was built for publication: Hypercontractivity, sum-of-squares proofs, and their applications