Bypassing UGC from Some Optimal Geometric Inapproximability Results

No abstract is available for this paper.

• Publication year

  2016

• Venue

  TALG

• Publication date

  2016-02-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2737729
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximation And Complexity In Numerical Optimization Continuous And Discrete Problems

  2016cited by this paper
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives

  2011cited by this paper
• Matrix Computations

  2011cited by this paper
• Rounding Semidefinite Programming Hierarchies via Global Correlation

  2011cited by this paper
• On the hardness of learning intersections of two halfspaces

  2011cited by this paper
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant

  2011cited by this paper
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems

  2010cited by this paper
• Spectral Algorithms for Unique Games

  2010cited by this paper
• Coresets and sketches for high dimensional subspace approximation problems

  2010cited by this paper
• Subexponential Algorithms for Unique Games and Related Problems

  2010cited by this paper
• Algorithms and hardness for subspace approximation

  2009influential reference
• Agnostic Learning of Monomials by Halfspaces Is Hard

  2009influential reference
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

  2009cited by this paper
• Optimal Long Code Test with One Free Bit

  2009cited by this paper
• Unique games on expanding constraint graphs are easy: extended abstract

  2008cited by this paper
• The UGC hardness threshold of the ℓp Grothendieck problem

  2008influential reference
• Vertex cover might be hard to approximate to within 2-epsilon

  2008cited by this paper
• Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes

  2008cited by this paper
• On hardness of learning intersection of two halfspaces

  2008cited by this paper
• Optimal algorithms and inapproximability results for every CSP?

  2008cited by this paper
• Gaussian Bounds for Noise Correlation of Functions

  2007cited by this paper
• Sampling-based dimension reduction for subspace approximation

  2007cited by this paper
• Efficient Subspace Approximation Algorithms

  2007cited by this paper
• Simulating Quantum Correlations with Finite Communication

  2007cited by this paper
• Approximating the Radii of Point Sets

  2007cited by this paper
• Approximating unique games

  2006cited by this paper
• Near-optimal algorithms for unique games

  2006cited by this paper
• A 3-query non-adaptive PCP with perfect completeness

  2006cited by this paper
• Integrality gaps for sparsest cut and minimum linear arrangement problems

  2006cited by this paper
• Approximation algorithms for unique games

  2005cited by this paper
• On non-approximability for quadratic programs

  2005influential reference
• HAPLOFREQ—Estimating Haplotype Frequencies Efficiently

  2005cited by this paper
• The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l/sub 1/

  2005cited by this paper
• Quadratic forms on graphs

  2005cited by this paper
• Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

  2004influential reference
• Approximating the cut-norm via Grothendieck's inequality

  2004cited by this paper
• Maximizing quadratic programs: extending Grothendieck's inequality

  2004cited by this paper
• Vertex cover might be hard to approximate to within 2-/spl epsiv/

  2003cited by this paper
• Projective clustering in high dimensions using core-sets

  2002cited by this paper
• Hardness results for coloring 3-colorable 3-uniform hypergraphs

  2002cited by this paper
• On the power of unique 2-prover 1-round games

  2002influential reference
• Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects

  2002cited by this paper
• Relaxations of Quadratic Programs in Operator Theory and System Analysis

  2001cited by this paper
• Inapproximability of some Geometric and Quadratic Optimization Problems

  2000cited by this paper
• On maximization of quadratic form over intersection of ellipsoids with common center

  1999cited by this paper
• Global quadratic optimization via conic relaxation

  1998cited by this paper
• Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint

  1998cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998cited by this paper
• A parallel repetition theorem

  1995cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper

• The quantum smooth label cover problem is undecidable

  2025cites this paper
• Guessing Efficiently for Constrained Subspace Approximation

  2025influential citation
• Root Ridge Leverage Score Sampling for ℓp Subspace Approximation

  2024cites this paper
• Hardness of Learning Boolean Functions from Label Proportions

  2024cites this paper
• On Approximability of the Permanent of PSD Matrices

  2024cites this paper
• The Generalized Matrix Norm Problem

  2023cites this paper
• New Subset Selection Algorithms for Low Rank Approximation: Offline and Online

  2023cites this paper
• Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem

  2022cites this paper
• Algorithms and Hardness for Learning Linear Thresholds from Label Proportions

  2022cites this paper
• The ℓp-Gaussian-Grothendieck problem with vector spins

  2021cites this paper
• The Quest for Strong Inapproximability Results with Perfect Completeness

  2021cites this paper
• A framework for quadratic form maximization over convex sets through nonconvex relaxations

  2021cites this paper
• On ℓp-Gaussian–Grothendieck Problem

  2021cites this paper
• Learnability of Linear Thresholds from Label Proportions

  2021cites this paper
• PR ] 1 0 D ec 2 02 1 The l p-Gaussian-Grothendieck problem with vector spins

  2021cites this paper
• On $\ell_p$-Gaussian-Grothendieck problem

  2020cites this paper
• Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness

  2019cites this paper
• Proposal On the Approximability of Injective Tensor Norms

  2019cites this paper
• Inapproximability of Matrix p→q Norms

  2018cites this paper
• A Greedy Algorithm for Subspace Approximation Problem

  2018cites this paper
• A PTAS for $\ell_p$-Low Rank Approximation

  2018influential citation
• Robust Subspace Approximation in a Stream

  2018cites this paper
• On Computing Centroids According to the p-Norms of Hamming Distance Vectors

  2018cites this paper
• Majority Is Asymptotically the Most Stable Resilient Function

  2017cites this paper
• Online Primal-Dual Algorithms with Configuration Linear Programs

  2017cites this paper
• Hardness of learning noisy halfspaces using polynomial thresholds

  2017cites this paper
• Gaussian bounds for noise correlation of resilient functions

  2017cites this paper
• New Hardness Results for Graph and Hypergraph Colorings

  2016cites this paper
• Approximation Resistance from Pairwise-Independent Subgroups

  2016cites this paper
• Input Sparsity and Hardness for Robust Subspace Approximation

  2015cites this paper
• On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation

  2015cites this paper
• Approximation algorithms and the hardness of approximation

  2014cites this paper
• Tight Hardness of the Non-commutative Grothendieck Problem

  2014cites this paper
• Approximation Resistance by Disguising Biased Distributions

  2014cites this paper
• Parity is Positively Useless

  2014cites this paper
• Column Subset Selection Problem is UG-hard

  2014cites this paper
• Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

  2014cites this paper
• On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems

  2013cites this paper
• Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs

  2013cites this paper