scientific article; zbMATH DE number 7053310

zbMath1421.68062MaRDI QIDQ5743431

Rishi Saket, Yi Wu, Prasad Raghavendra, Venkatesan Guruswami

Publication date: 10 May 2019

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

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

Related Items (3)

Column subset selection problem is UG-hard ⋮ On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation ⋮ Gaussian bounds for noise correlation of resilient functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On maximization of quadratic form over intersection of ellipsoids with common center
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Hardness of Reconstructing Multivariate Polynomials over Finite Fields
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• The UGC Hardness Threshold of the L_p Grothendieck Problem
• Subexponential Algorithms for Unique Games and Related Problems
• Sampling-based dimension reduction for subspace approximation
• On the power of unique 2-prover 1-round games
• Projective clustering in high dimensions using core-sets
• Agnostic Learning of Monomials by Halfspaces Is Hard
• Approximating the Radii of Point Sets
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Approximating the Cut-Norm via Grothendieck's Inequality
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Quadratic forms on graphs

This page was built for publication: