Fetching the paper…
Reading the bibliography…
We survey connections of the Grothendieck inequality and its variants to combinatorial optimization and computational complexity.
Résumé de la théorie métrique des produits tensoriels topologiques
A. Grothendieck · 1953
Earlier work this paper cites.
On the evolution of random graphs
P. Erdős and A. Rényi · 1960
Earlier work this paper cites.
Absolutely summing operators in L p L_{p} -spaces and their applications
J. Lindenstrauss and A. Pełczyński · 1968
Earlier work this paper cites.
On the complete subgraphs of a random graph
D. W. Matula · 1970
Earlier work this paper cites.
A proof of the Grothendieck inequality
R. E. Rietz · 1974
Earlier work this paper cites.
On an inequality of von Neumann and an application of the metric theory of tensor products to operators theory
N. T. Varopoulos · 1974
Earlier work this paper cites.
Informational complexity and effective methods for the solution of convex extremal problems
D. B. Judin and A. S. Nemirovskiĭ · 1976
Earlier work this paper cites.
Sur la constante de Grothendieck
J.-L. Krivine · 1977
Earlier work this paper cites.
Grothendieck’s theorem for noncommutative C ∗ C^{\ast} -algebras, with an appendix on Grothendieck’s constants
G. Pisier · 1978
Earlier work this paper cites.
Regular partitions of graphs
E. Szemerédi · 1978
Earlier work this paper cites.
The von Neumann inequality for polynomials in several Hilbert-Schmidt operators
A. Tonge · 1978
Earlier work this paper cites.
Multidimensional extensions of the Grothendieck inequality and applications
R. C. Blei · 1979
Earlier work this paper cites.
Computers and intractability
M. R. Garey and D. S. Johnson · 1979
Earlier work this paper cites.
Constantes de Grothendieck et fonctions de type positif sur les sphères
J.-L. Krivine · 1979
Earlier work this paper cites.
On the Shannon capacity of a graph
L. Lovász · 1979
Earlier work this paper cites.
On the ground states of the frustration model of a spin glass by a matching method of graph theory
I. Bieche, R. Maynard, R. Rammal, and J.-P. Uhry · 1980
Earlier work this paper cites.
On the computational complexity of Ising spin glass models
F. Barahona · 1982
Earlier work this paper cites.
The asymptotic behaviour of Lovász’ θ \theta function for random graphs
F. Juhász · 1982
Earlier work this paper cites.
Computer-intractability of the frustration model of a spin glass
C. P. Bachas · 1984
Earlier work this paper cites.
Matrix norms related to Grothendieck’s inequality
A. M. Davie · 1985
Earlier work this paper cites.
The Grothendieck inequality for bilinear forms on C ∗ C^{\ast} -algebras
U. Haagerup · 1985
Earlier work this paper cites.
Quantum analogues of Bell’s inequalities. The case of two spatially divided domains
B. S. Tsirelson · 1985
Earlier work this paper cites.
Matching theory
L. Lovász and M. D. Plummer · 1986
Earlier work this paper cites.
Factorization of linear operators and geometry of Banach spaces
G. Pisier · 1986
Earlier work this paper cites.
The complex Grothendieck inequality for 2 × 2 2\times 2 matrices
A. Tonge · 1986
Earlier work this paper cites.
A new upper bound for the complex Grothendieck constant
U. Haagerup · 1987
Earlier work this paper cites.
Summing and nuclear norms in Banach space theory
G. J. O. Jameson · 1987
Earlier work this paper cites.
Completely bounded multilinear maps and Grothendieck’s inequality
R. R. Smith · 1988
Earlier work this paper cites.
On the complex Grothendieck constant in the n n -dimensional case
H. König · 1990
Earlier work this paper cites.
Optimization, approximation, and complexity classes
C. H. Papadimitriou and M. Yannakakis · 1991
Earlier work this paper cites.
A new lower bound on the real Grothendieck constant
J. A. Reeds · 1991
Earlier work this paper cites.
Some remarks on the Grothendieck inequality
H. König · 1992
Earlier work this paper cites.
Geometric algorithms and combinatorial optimization
M. Grötschel, L. Lovász, and A. Schrijver · 1993
Earlier work this paper cites.
The algorithmic aspects of the regularity lemma
N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster · 1994
Earlier work this paper cites.
Bell inequalities, Grothendieck’s constant, and root two
P. C. Fishburn and J. A. Reeds · 1994
Earlier work this paper cites.
Repeated communication and Ramsey graphs
N. Alon and A. Orlitsky · 1995
Earlier work this paper cites.
Absolutely summing operators
J. Diestel, H. Jarchow, and A. Tonge · 1995
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Matrix computations
G. H. Golub and C. F. Van Loan · 1996
Earlier work this paper cites.
Eigenvalue optimization
A. S. Lewis and M. L. Overton · 1996
Cited alongside, same era.
Lower bounds of tower type for Szemerédi’s uniformity lemma
W. T. Gowers · 1997
Cited alongside, same era.
Szemerédi’s regularity lemma for sparse graphs
Y. Kohayakawa · 1997
Cited alongside, same era.
Introduction to the theory of computation
M. Sipser · 1997
Cited alongside, same era.
Approximate graph coloring by semidefinite programming
D. Karger, R. Motwani, and M. Sudan · 1998
Cited alongside, same era.
Semidefinite relaxation and nonconvex quadratic optimization
Y. Nesterov · 1998
Cited alongside, same era.
Parameterized complexity
R. G. Downey and M. R. Fellows · 1999
Complexity measures of sign matrices
N. Linial, S. Mendelson, G. Schechtman, and A. Shraibman · 2007
Later among the works it cites.
Szemerédi’s lemma for the analyst
L. Lovász and B. Szegedy · 2007
Later among the works it cites.
Advances in convex optimization: conic programming
A. Nemirovski · 2007
Later among the works it cites.
A dependence maximization view of clustering
L. Song, A. Smola, A. Gretton, and K. A. Borgwardt · 2007
Later among the works it cites.
The Grothendieck constant of random and pseudo-random graphs
N. Alon and E. Berger · 2008
Later among the works it cites.
The metric theory of tensor products
J. Diestel, J. H. Fourie, and J. Swart · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Quick approximation to matrices and applications
A. Frieze and R. Kannan · 1999
Cited alongside, same era.
On maximization of quadratic form over intersection of ellipsoids with common center
A. Nemirovski, C. Roos, and T. Terlaky · 1999
Cited alongside, same era.
The probabilistic method
N. Alon and J. H. Spencer · 2000
Cited alongside, same era.
Semidefinite programming relaxations of nonconvex quadratic optimization
Y. Nesterov, H. Wolkowicz, and Y. Ye · 2000
Cited alongside, same era.
Analysis in integer and fractional dimensions
R. Blei · 2001
Cited alongside, same era.
V. Guruswami, R. Manokaran, and P. Raghavendra · 2008
Later among the works it cites.
Entangled games are hard to approximate
J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick · 2008
Later among the works it cites.
Linear equations modulo 2 and the L 1 L_{1} diameter of convex bodies
S. Khot and A. Naor · 2008
Later among the works it cites.
Unbounded violation of tripartite Bell inequalities
D. Pérez-García, M. M. Wolf, C. Palazuelos, I. Villanueva, and M. Junge · 2008
Later among the works it cites.
New Bell inequalities for the singlet state: going beyond the Grothendieck bound
I. Pitowsky · 2008
Later among the works it cites.
Optimal algorithms and inapproximability results for every CSP?
P. Raghavendra · 2008
Later among the works it cites.
Computational complexity
S. Arora and B. Barak · 2009
Later among the works it cites.
Regularity lemmas and combinatorial algorithms
N. Bansal and R. Williams · 2009
Later among the works it cites.
A generalized Grothendieck inequality and entanglement in XOR games
J. Briet, H. Buhrman, and B. Toner · 2009
Later among the works it cites.
An efficient sparse regularity concept
A. Coja-Oghlan, C. Cooper, and A. Frieze · 2009
Later among the works it cites.
Approximate kernel clustering
S. Khot and A. Naor · 2009
Later among the works it cites.
SDP gaps and UGC-hardness for max-cut-gain
S. Khot and R. O’Donnell · 2009
Later among the works it cites.
Lower bounds on quantum multiparty communication complexity
T. Lee, G. Schechtman, and A. Shraibman · 2009
Later among the works it cites.
Learning complexity vs. communication complexity
N. Linial and A. Shraibman · 2009
Later among the works it cites.
Lower bounds in communication complexity based on factorization norms
N. Linial and A. Shraibman · 2009
Later among the works it cites.
An approximation scheme for quadratic form maximization on convex bodies
A. Naor and G. Schechtman · 2009
Later among the works it cites.
Towards computing the Grothendieck constant
P. Raghavendra and D. Steurer · 2009
Later among the works it cites.
Simulating quantum correlations with finite communication
O. Regev and B. Toner · 2009
Later among the works it cites.
Quasi-randomness and algorithmic regularity for graphs with general degree distributions
N. Alon, A. Coja-Oghlan, H. Hàn, M. Kang, V. Rödl, and M. Schacht · 2010
Later among the works it cites.
Grothendieck inequalities for semidefinite programs with rank constraint
J. Briet, F. M. de Oliveira Filho, and V. F · 2010
Later among the works it cites.
The positive semidefinite Grothendieck problem with rank constraint
J. Briët, F. M. de Oliveira Filho, and F. Vallentin · 2010
Later among the works it cites.
Bypassing UGC from some optimal geometric inapproximability results
V. Guruswami, P. Raghavendra, R. Saket, and Y. Wu · 2010
Later among the works it cites.
On the unique games conjecture (invited survey)
S. Khot · 2010
Later among the works it cites.
Sharp kernel clustering algorithms and their associated Grothendieck inequalities
S. Khot and A. Naor · 2010
Later among the works it cites.
The UGC hardness threshold of the L p L_{p} Grothendieck problem
G. Kindler, A. Naor, and G. Schechtman · 2010
Later among the works it cites.
Approximating matrix p p -norms
A. Bhaskara and A. Vijayaraghavan · 2011
Closest in time.
The Grothendieck constant is strictly smaller than Krivine’s bound
M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor · 2011
Closest in time.
Bounds for graph regularity and removal lemmas
D. Conlon and J. Fox · 2011
Closest in time.
Solution of the propeller conjecture in ℝ 3 \mathbb{R}^{3}
S. Heilman, A. Jagannath, and A. Naor · 2011
Closest in time.
A two prover one round game with strong soundness
S. Khot and S. Safra · 2011
Closest in time.
Computing the Grothendieck constant of some graph classes
M. Laurent and A. Varvitsiotis · 2011
Closest in time.
Grothendieck’s theorem, past and present
G. Pisier · 2011
Closest in time.