Approximating the cut-norm via Grothendieck's inequality
DOI10.1145/1007352.1007371zbMATH Open1192.68866OpenAlexW1990811538WikidataQ105337412 ScholiaQ105337412MaRDI QIDQ3580948FDOQ3580948
Authors: Noga Alon, Assaf Naor 
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007371
Recommendations
- Approximating the Cut-Norm via Grothendieck's Inequality
- Efficient rounding for the noncommutative Grothendieck inequality
- Efficient Rounding for the Noncommutative Grothendieck Inequality
- The Grothendieck constant is strictly smaller than Krivine's bound
- Grothendieck-type inequalities in combinatorial optimization
Combinatorial optimization (90C27) Semidefinite programming (90C22) Approximation algorithms (68W25) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Algorithms for approximation of functions (65D15)
Cited In (25)
- Fast Heuristics and Approximation Algorithms
- Approximating the Cut-Norm via Grothendieck's Inequality
- The bipartite Boolean quadric polytope
- Computing the Grothendieck constant of some graph classes
- Efficient algorithms for privately releasing marginals via convex relaxations
- The Hilbertian tensor norm and entangled two-prover games
- A deterministic algorithm for the Frieze-Kannan regularity lemma
- Quadratic forms on graphs
- Unbounded violation of tripartite Bell inequalities
- Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
- On computational capabilities of Ising machines based on nonlinear oscillators
- Cut norm discontinuity of triangular truncation of graphons
- Approximating the little Grothendieck problem over the orthogonal and unitary groups
- A unified view of graph regularity via matrix decompositions
- A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
- Title not available (Why is that?)
- On approximating complex quadratic optimization problems via semidefinite programming relaxations
- The Bipartite QUBO
- A note on the Hausdorff distance between norm balls and their linear maps
- Efficient Rounding for the Noncommutative Grothendieck Inequality
- The Grothendieck inequality revisited
- Sum-of-squares hierarchies for binary polynomial optimization
- Sum-of-squares hierarchies for binary polynomial optimization
- An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices
- Non-unique games over compact groups and orientation estimation in cryo-EM
This page was built for publication: Approximating the cut-norm via Grothendieck's inequality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580948)
