scientific article; zbMATH DE number 7053310

MaRDI QIDQ5743431zbMATH OpenFDO

Authors Prasad Raghavendra, Rishi Saket, Yi Wu, Venkatesan Guruswami

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095174

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Bypassing UGC from some optimal geometric inapproximability results
• Near-optimal UGC-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
• Unifying known lower bounds via geometric complexity theory
• Some optimal inapproximability results
• scientific article; zbMATH DE number 1559516
• Explicit lower bounds via geometric complexity theory
• scientific article; zbMATH DE number 431985
• Approximations and optimal geometric divide-and-conquer
• Approximation algorithms for geometrical distance problems that are not solvable exactly
• scientific article; zbMATH DE number 4123298

Cites work

• Algorithms and hardness for subspace approximation
• Approximating the Cut-Norm via Grothendieck's Inequality
• Approximating the Radii of Point Sets
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Coresets and sketches for high dimensional subspace approximation problems
• Efficient subspace approximation algorithms
• Hardness of Reconstructing Multivariate Polynomials over Finite Fields
• scientific article; zbMATH DE number 5485536 (Why is no real title available?)
• scientific article; zbMATH DE number 5485546 (Why is no real title available?)
• scientific article; zbMATH DE number 1303558 (Why is no real title available?)
• scientific article; zbMATH DE number 1560333 (Why is no real title available?)
• scientific article; zbMATH DE number 1751736 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• On maximization of quadratic form over intersection of ellipsoids with common center
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Projective clustering in high dimensions using core-sets
• Quadratic forms on graphs (extended abstract)
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Sampling-based dimension reduction for subspace approximation
• Subexponential algorithms for unique games and related problems
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Unique games on expanding constraint graphs are easy (extended abstract)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(10)

• Gaussian bounds for noise correlation of resilient functions
• Column subset selection problem is UG-hard
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• The UGC hardness threshold of the l_p Grothendieck problem
• scientific article; zbMATH DE number 3974286 (Why is no real title available?)
• Bypassing UGC from some optimal geometric inapproximability results
• A periodic isoperimetric problem related to the unique games conjecture
• On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
• Algorithms and hardness for subspace approximation
• New subset selection algorithms for low rank approximation: offline and online

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743431)