Grothendieck-Type Inequalities in Combinatorial Optimization

DOI10.1002/cpa.21398zbMath1248.46047arXiv1108.2464OpenAlexW2964235642MaRDI QIDQ2892967

Assaf Naor, Subhash A. Khot

Publication date: 25 June 2012

Published in: Communications on Pure and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraphinteger programmingcombinatorial optimisationunique games conjectureGrothendieck constantGrothendieck inequalitykernel clusteringSzemerédi partitionscut normFrieze-Kannan matrix decompositionslinear equations modulo~\(2\)maximum acyclic subgraphspropeller conjecture

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Combinatorial optimization (90C27) Local theory of Banach spaces (46B07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Miscellaneous inequalities involving matrices (15A45) Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (26)

Convex Bodies Associated to Tensor Norms ⋮ Failure of the trilinear operator space Grothendieck theorem ⋮ Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms ⋮ A general theory of tensor products of convex sets in Euclidean spaces ⋮ The Bipartite QUBO ⋮ The \(\ell^p\)-Gaussian-Grothendieck problem with vector spins ⋮ Solution of the propeller conjecture in \(\mathbb R^3\) ⋮ Low correlation noise stability of symmetric sets ⋮ Phase transitions in semidefinite relaxations ⋮ Computing the Partition Function of a Polynomial on the Boolean Cube ⋮ Unnamed Item ⋮ Complexity and nonlinear semidefinite programming reformulation of \(\ell_1\)-constrained nonconvex quadratic optimization ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND ⋮ A hyperspace of convex bodies arising from tensor norms ⋮ Quasirandom Cayley graphs ⋮ Simplicial faces of the set of correlation matrices ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ The Grothendieck Inequality Revisited ⋮ The global convergence of the nonlinear power method for mixed-subordinate matrix norms ⋮ On fractional cut covers ⋮ Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor ⋮ The Complexity of Differential Privacy ⋮ A new semidefinite relaxation for \(L_{1}\)-constrained quadratic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the Grothendieck constant of some graph classes
• The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
• A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
• A characterization for sparse \(\varepsilon\)-regular pairs
• Szemerédi's lemma for the analyst
• Complexity measures of sign matrices
• The Grothendieck constant of random and pseudo-random graphs
• The Grothendieck inequality for bilinear forms on \(C^*\)-algebras
• A new upper bound for the complex Grothendieck constant
• Quick approximation to matrices and applications
• Multidimensional extensions of the Grothendieck inequality and applications
• Optimization, approximation, and complexity classes
• A proof of the Grothendieck inequality
• Grothendieck's theorem for noncommutative \(C^*\)-algebras, with an appendix on Grothendieck's constants
• Constantes de Grothendieck et fonctions de type positif sur les sphères
• Lower bounds of tower type for Szemerédi's uniformity lemma
• On an inequality of von Neumann and an application of the metric theory of tensor products to operators theory. (Appendix by S. Kaijser and N. Th. Varopoulos.)
• Random sampling and approximation of MAX-CSPs
• Bounds for graph regularity and removal lemmas
• On maximization of quadratic form over intersection of ellipsoids with common center
• Unbounded violation of tripartite Bell inequalities
• Clustering with qualitative information
• The Grothendieck Inequality Revisited
• An Efficient Sparse Regularity Concept
• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Entangled Games Are Hard to Approximate
• The UGC Hardness Threshold of the L_p Grothendieck Problem
• Grothendieck inequalities for semidefinite programs with rank constraint
• Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies
• Approximate Kernel Clustering
• Lower Bounds in Communication Complexity
• New Bell inequalities for the singlet state: Going beyond the Grothendieck bound
• Learning Complexity vs Communication Complexity
• Simulating Quantum Correlations with Finite Communication
• The Positive Semidefinite Grothendieck Problem with Rank Constraint
• Completely Bounded Multilinear Maps and Grothendieck's Inequality
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• The Von Neumann Inequality for Polynomials in Several Hilbert-Schmidt Operators
• Bell Inequalities, Grothendieck’s Constant, and Root Two
• The Algorithmic Aspects of the Regularity Lemma
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• An Optimal Algorithm for Checking Regularity
• Repeated communication and Ramsey graphs
• Bypassing UGC from Some Optimal Geometric Inapproximability Results
• Regularity Lemmas and Combinatorial Algorithms
• Computational Complexity
• Grothendieck’s Theorem, past and present
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Approximating the Cut-Norm via Grothendieck's Inequality
• Quantum correlation and Grothendieck's constant
• The Grothendieck Constant is Strictly Smaller than Krivine's Bound
• On the advantage over a random assignment
• Quadratic forms on graphs
• Lower bounds in communication complexity based on factorization norms

This page was built for publication: Grothendieck-Type Inequalities in Combinatorial Optimization