Approximating the cut-norm via Grothendieck's inequality

DOI10.1145/1007352.1007371MaRDI QIDQ3580948zbMATHOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

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)

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

Cited in

(28)

• Zero-one rounding of singular vectors
• Efficient rounding for the noncommutative Grothendieck inequality
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• On computational capabilities of Ising machines based on nonlinear oscillators
• A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
• Approximating the Cut-Norm via Grothendieck's Inequality
• A unified view of graph regularity via matrix decompositions
• The bipartite Boolean quadric polytope
• Non-unique games over compact groups and orientation estimation in cryo-EM
• Computing the Grothendieck constant of some graph classes
• A note on the Hausdorff distance between norm balls and their linear maps
• Cut norm discontinuity of triangular truncation of graphons
• Fast heuristics and approximation algorithms
• Quadratic forms on graphs
• The bipartite QUBO
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• The Hilbertian tensor norm and entangled two-prover games
• Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
• Approximating sparse binary matrices in the cut-norm
• scientific article; zbMATH DE number 7758351 (Why is no real title available?)
• Unbounded violation of tripartite Bell inequalities
• Efficient Rounding for the Noncommutative Grothendieck Inequality
• On approximating complex quadratic optimization problems via semidefinite programming relaxations
• 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
• Efficient algorithms for privately releasing marginals via convex relaxations

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)