Vertex cover might be hard to approximate to within \(2 - \varepsilon \) (Q2475406): Difference between revisions

@@ Property / author @@
-Subhash A. Khot
@@ Property / author: Subhash A. Khot / rank @@
-Normal rank
@@ Property / author @@
+Subhash A. Khot
@@ Property / author: Subhash A. Khot / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jcss.2007.06.019
+Normal rank
@@ Property / OpenAlex ID @@
+W2137118456
@@ Property / OpenAlex ID: W2137118456 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q94993767
@@ Property / Wikidata QID: Q94993767 / rank @@
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Probabilistic checking of proofs
@@ Property / cites work: Probabilistic checking of proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Near-optimal algorithms for unique games
@@ Property / cites work: Near-optimal algorithms for unique games / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating Multicut and Sparsest-Cut
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+Conditional hardness for approximate coloring
@@ Property / cites work: Conditional hardness for approximate coloring / rank @@
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimum vertex cover
+Normal rank
@@ Property / cites work @@
+Boolean functions with low average sensitivity depend on few coordinates
+Normal rank
@@ Property / cites work @@
+Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
+Normal rank
@@ Property / cites work @@
+Approximating unique games
@@ Property / cites work: Approximating unique games / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness of Approximate Hypergraph Coloring
@@ Property / cites work: Hardness of Approximate Hypergraph Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Q4737227
@@ Property / cites work: Q4737227 / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / 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 @@
+Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
+Normal rank
@@ Property / cites work @@
+The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ             <sub>1</sub>
+Normal rank
@@ Property / cites work @@
+Q4083487
@@ Property / cites work: Q4083487 / rank @@
+Normal rank
@@ Property / cites work @@
+A Parallel Repetition Theorem
@@ Property / cites work: A Parallel Repetition Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+An approximate zero-one law
@@ Property / cites work: An approximate zero-one law / rank @@
+Normal rank
@@ Property / cites work @@
+Non-approximability results for optimization problems on bounded degree instances
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2475406