New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover (Q2943894): Difference between revisions

@@ Property / arXiv ID @@
+.5648
@@ Property / arXiv ID: 1210.5648 / rank @@
+Normal rank
@@ Property / cites work @@
+Subexponential Algorithms for Unique Games and Related Problems
+Normal rank
@@ Property / cites work @@
+Approximation resistant predicates from pairwise independence
+Normal rank
@@ Property / cites work @@
+A New Point of NP-Hardness for 2-to-1 Label Cover
@@ Property / cites work: A New Point of NP-Hardness for 2-to-1 Label Cover / rank @@
+Normal rank
@@ Property / cites work @@
+Rounding Semidefinite Programming Hierarchies via Global Correlation
+Normal rank
@@ Property / cites work @@
+Conditional Hardness for Approximate Coloring
@@ Property / cites work: Conditional Hardness for Approximate Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
+Normal rank
@@ Property / cites work @@
+Improved Inapproximability Results for Maximum k-Colorable Subgraph
+Normal rank
@@ Property / cites work @@
+Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
+Normal rank
@@ Property / cites work @@
+SDP Gaps for 2-to-1 and Other Label-Cover Variants
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of unique 2-prover 1-round games
@@ Property / cites work: On the power of unique 2-prover 1-round games / rank @@
+Normal rank
@@ Property / cites work @@
+Two-query PCP with subconstant error
@@ Property / cites work: Two-query PCP with subconstant error / rank @@
+Normal rank
@@ Property / cites work @@
+A new point of NP-hardness for unique games
@@ Property / cites work: A new point of NP-hardness for unique games / rank @@
+Normal rank
@@ Property / cites work @@
+The hardness of approximation: Gap location
@@ Property / cites work: The hardness of approximation: Gap location / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549708
@@ Property / cites work: Q3549708 / rank @@
+Normal rank
@@ Property / cites work @@
+Gadgets, Approximation, and Linear Programming
@@ Property / cites work: Gadgets, Approximation, and Linear Programming / rank @@
+Normal rank