Approximating the cut-norm via Grothendieck's inequality

DOI10.1145/1007352.1007371zbMath1192.68866OpenAlexW1990811538WikidataQ105337412 ScholiaQ105337412MaRDI QIDQ3580948

Assaf Naor, Noga Alon

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

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Algorithms for approximation of functions (65D15) Approximation algorithms (68W25)

Related Items

Fast Heuristics and Approximation Algorithms, The Bipartite QUBO, 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, On approximating complex quadratic optimization problems via semidefinite programming relaxations, The bipartite Boolean quadric polytope, A note on the Hausdorff distance between norm balls and their linear maps, A unified view of graph regularity via matrix decompositions, Computing the Grothendieck constant of some graph classes, A generalized Grothendieck inequality and nonlocal correlations that require high entanglement, An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices, Unnamed Item, The Hilbertian tensor norm and entangled two-prover games, Quadratic forms on graphs, Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem, Sum-of-squares hierarchies for binary polynomial optimization, Unbounded violation of tripartite Bell inequalities, Sum-of-squares hierarchies for binary polynomial optimization, The Grothendieck Inequality Revisited, A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma, Non-unique games over compact groups and orientation estimation in cryo-EM, Efficient algorithms for privately releasing marginals via convex relaxations