Approximating the Cut-Norm via Grothendieck's Inequality
From MaRDI portal
Publication:5470714
DOI10.1137/S0097539704441629zbMath1096.68163OpenAlexW3023108254MaRDI QIDQ5470714
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704441629
semidefinite programmingapproximation algorithmsGrothendieck's inequalitycut-normSzemerédi partitions
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 (57)
Graph partitioning by correspondence analysis and taxicab correspondence analysis ⋮ Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Fast Heuristics and Approximation Algorithms ⋮ The Bipartite QUBO ⋮ Integrating tabu search and VLSN search to develop enhanced algorithms: a case study using bipartite Boolean quadratic programs ⋮ Unnamed Item ⋮ The Communication Complexity of Non-signaling Distributions ⋮ The \(\ell^p\)-Gaussian-Grothendieck problem with vector spins ⋮ Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem ⋮ Stochastic budget optimization in internet advertising ⋮ Parallel stochastic gradient algorithms for large-scale matrix completion ⋮ Approximation algorithms for discrete polynomial optimization ⋮ The convex geometry of linear inverse problems ⋮ Norms of random matrices: local and global problems ⋮ On solving biquadratic optimization via semidefinite relaxation ⋮ Approximation algorithms for indefinite complex quadratic maximization problems ⋮ On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ Central limit theorems for global and local empirical measures of diffusions on Erdős-Rényi graphs ⋮ Approximating sparse quadratic programs ⋮ Weakly interacting oscillators on dense random graphs ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Two proposals for robust PCA using semidefinite programming ⋮ On a Question of N. Th. Varopoulos and the constant $C_2(n)$ ⋮ Semidefinite Approximation of Closed Convex Set ⋮ Extremal results in sparse pseudorandom graphs ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking ⋮ Grothendieck’s Theorem, past and present ⋮ Approximation bounds for trilinear and biquadratic optimization problems over nonconvex constraints ⋮ Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms ⋮ The road to deterministic matrices with the restricted isometry property ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Graph summarization with quality guarantees ⋮ THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND ⋮ Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing ⋮ Markov chain methods for the bipartite Boolean quadratic programming problem ⋮ Complexity and algorithms for finding a subset of vectors with the longest sum ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ Approximation methods for complex polynomial optimization ⋮ On the Complexity of Robust PCA and ℓ1-Norm Low-Rank Matrix Approximation ⋮ Approximability of the Problem of Finding a Vector Subset with the Longest Sum ⋮ On the tensor spectral \(p\)-norm and its dual norm via partitions ⋮ Quantum XOR Games ⋮ Approximate Kernel Clustering ⋮ Inhomogeneous polynomial optimization over a convex set: An approximation approach ⋮ Moments Tensors, Hilbert's Identity, and k-wise Uncorrelated Random Variables ⋮ Probability Bounds for Polynomial Functions in Random Variables ⋮ Binary Component Decomposition Part I: The Positive-Semidefinite Case ⋮ Hardness and Approximation Results for Lp-Ball Constrained Homogeneous Polynomial Optimization Problems ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor ⋮ Unnamed Item ⋮ Some applications of hypercontractive inequalities in quantum information theory ⋮ Control analysis and design via randomised coordinate polynomial minimisation ⋮ Some new aspects of taxicab correspondence analysis ⋮ The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases ⋮ Long time dynamics for interacting oscillators on graphs
This page was built for publication: Approximating the Cut-Norm via Grothendieck's Inequality
