Imperfect gaps in Gap-ETH and PCPs (Q5091784): Difference between revisions

@@ label / en / label / en @@
+Imperfect gaps in Gap-ETH and PCPs
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Hardness amplification for entangled games via anchoring
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Short PCPs with Polylog Query Complexity
@@ Property / cites work: Short PCPs with Polylog Query Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
+Normal rank
@@ Property / cites work @@
+Approximation resistance from pairwise independent subgroups
+Normal rank
@@ Property / cites work @@
+The PCP theorem by gap amplification
@@ Property / cites work: The PCP theorem by gap amplification / rank @@
+Normal rank
@@ Property / cites work @@
+Towards a proof of the 2-to-1 games conjecture?
@@ Property / cites work: Towards a proof of the 2-to-1 games conjecture? / rank @@
+Normal rank
@@ Property / cites work @@
+ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
+Normal rank
@@ Property / cites work @@
+A Chernoff Bound for Random Walks on Expander Graphs
+Normal rank
@@ Property / cites work @@
+A Sample of Samplers: A Computational Perspective on Sampling
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
+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 @@
+Q5111409
@@ Property / cites work: Q5111409 / rank @@
+Normal rank
@@ Property / cites work @@
+Parallel Repetition in Projection Games and a Concentration Bound
+Normal rank
@@ Property / cites work @@
+A Parallel Repetition Theorem
@@ Property / cites work: A Parallel Repetition Theorem / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2966552573
@@ Property / OpenAlex ID: W2966552573 / rank @@
+Normal rank
@@ Property / title @@
+Imperfect gaps in Gap-ETH and PCPs (English)
@@ Property / title: Imperfect gaps in Gap-ETH and PCPs (English) / rank @@
+Normal rank