Approximating the cut-norm via Grothendieck's inequality

By Noga Alon, Assaf Naor. Symposium on the Theory of Computing, 2004

360 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design

View Paper: https://www.semanticscholar.org/paper/ddf22c7aa8881b9963a3a6a3189c4710e91a7eea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

Citations in the corpus

Consequences and limits of nonlocal strategies (2004, methodology): “This integer quadratic program is MAXSNP hard [1].”
Grothendieck's Theorem, past and present (2011, background): “The papers [4, 5] ignited a lot of interest in the computer science literature.”
Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing (2007, background): “A better polynomial-time computable approximation is the Grothendieck norm, which approximates the cut-norm within a constant factor (see [5]).”
Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate (2010, methodology): “We refer to this norm, which is denoted by ‖A‖∞7→1 in (Alon & Naor, 2004), as the pseudo-cut-norm of A and denote it simply by ‖A‖.”
Graphons, cut norm and distance, couplings and rearrangements (2010, methodology): “See [3] for an algorithmic use of the version ‖ · ‖ ,H of the cut norm and Grothendieck’s inequality.”
Parallel stochastic gradient algorithms for large-scale matrix completion (2013, background): “To see that no lower value is achievable requires an appeal to semidefinite programming and is proven in Recht et al. [32].”
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization (2013, background): “For example, maximizing uv T , M over vectors u ∞ ≤ 1 and v ∞ ≤ 1 for a given matrix M amounts to computing the cut-norm M ∞→1 , which is NP-hard (Alon & Naor, 2006).”
The Convex Geometry of Linear Inverse Problems (2010, background): “These decompositions are useful, for instance, in actually computing the rank-one binary vectors optimized in semidefinite relaxations of combinatorial algorithms [2, 37, 55], or in the computation of tensor decompositions from incomplete data [47].”
On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation (2015, neutral): “the following, we prove that computing the cut norm of {−1,+1}m×n matrices is NP-hard hence rank-one BMF and rank-one ℓ 0-LRA are also NP-hard. First, let us consider the following norm introduced in [1]: for A ∈ Rm×n ||A||∞→1 = max u∈{−1,+1}m,v∈{−1,+1}n uTAv. (3.1) To the best of our knowledge, sol”
Relaxations for inference in restricted Boltzmann machines (2013, background): “Even the cases where A encodes an RBM are NP-hard in general (Alon & Naor, 2006).”
Iterative Constructions and Private Data Release (2011, methodology): “There is a constant-factor approximation algorithm of Alon and Naor for the cut norm problem [AN06]; using this we can solve the LP above to within constant factors of optimum.”
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem (2007, neutral): “The following observation is due to Alon and Naor [ 2 ].”