Approximating the cut-norm via Grothendieck's inequality

DOI10.1145/1007352.1007371MaRDI QIDQ3580948zbMATH OpenOpenAlexWikidataFDO

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

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

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

(31)

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