2012/01/17 by Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket +1 · 1 citation
Mathematics · Computer Science · #Statistical Methods and Inference #Machine Learning and Algorithms #Computational Geometry and Mesh Generation #Combinatorics #Mathematics #Hardness of approximation #Conjecture #Ball (mathematics) #Approximation algorithm #Bijection #Discrete mathematics
paper · doi:10.1137/1.9781611973099.58
openalex publication_date 2012/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance nevertheless seems critical in these proofs. In this work we bypass the need for UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case. The first problem, known as the Lp Subspace Approximation, is a generalization of the classic least squares regression problem. Here, the input consists of a set of points S = a1, …, am ⊆ ℝn and a parameter k (possibly depending on n). The goal is to find a subspace H of ℝn of dimension k that minimizes the ℓp norm of the Euclidean distances to the points in S. For p = 2, k = n − 1, this reduces to the least squares regression problem, while for p = ∞, k = 0 it reduces to the problem of finding a ball of minimum radius enclosing all the points. We show that for any fixed p (2 < p < ∞), and for k = n − 1, it is NP-hard to approximate this problem to within a factor of γp − ∊ for constant ∊ > 0, where γp is the pth norm of a standard Gaussian random variable. This matches the γp approximation algorithm obtained by Deshpande, Tulsiani and Vishnoi [9] who also showed the same hardness result under the Unique Games Conjecture. The second problem we study is the related Lp Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor and Schechtman [24]. Here, the input is a multilinear quadratic form σni,j=1 aijxixj and the goal is to maximize the quadratic form over the ℓp unit ball, namely all x with σni=1 |xi|p = 1. The problem is polynomial time solvable for p = 2. We show that for any constant p (2 < p < ∞), it is NP-hard to approximate the quadratic form to within a factor of γ2p − ∊ for any ∊ > 0. The same hardness factor was shown under the UGC in [24]. We also obtain a γ2p-approximation algorithm for the problem using the convex relaxation of the problem defined by [24]. A γ2p approximation algorithm has also been independently obtained by Naor and Schechtman [27]. These are the first approximation thresholds, proven under P ≠ NP, that involve the Gaussian random variable in a fundamental way. Note that the problem statements themselves have no mention of Gaussians.