Bypassing UGC from some optimal geometric inapproximability results

DOI10.1145/2737729MaRDI QIDQ4962201zbMATH OpenOpenAlexFDO

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

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2737729

zbMATH Keywords

label coverNP-hardnesssubspace approximation

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

• scientific article; zbMATH DE number 7053310
• Algorithms and hardness for subspace approximation
• The UGC hardness threshold of the l_p Grothendieck problem
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

Cited in

(15)

• The \(\ell^p\)-Gaussian-Grothendieck problem with vector spins
• Grothendieck-type inequalities in combinatorial optimization
• 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?)
• The quest for strong inapproximability results with perfect completeness
• On computing centroids according to the p-norms of Hamming distance vectors
• A greedy algorithm for subspace approximation problem
• Algorithms and hardness for subspace approximation
• scientific article; zbMATH DE number 7053310 (Why is no real title available?)
• Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
• The generalized matrix norm problem
• Hardness of learning Boolean functions from label proportions
• Hardness of learning Boolean functions from label proportions
• Guessing efficiently for constrained subspace approximation

This page was built for publication: Bypassing UGC from some optimal geometric inapproximability results

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