Query-Efficient Dictatorship Testing with Perfect Completeness (Q4933378): Difference between revisions

@@ 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 @@
+A Hypergraph Dictatorship Test with Perfect Completeness
+Normal rank
@@ Property / cites work @@
+Conditional Hardness for Approximate Coloring
@@ Property / cites work: Conditional Hardness for Approximate Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+STACS 2005
@@ Property / cites work: STACS 2005 / rank @@
+Normal rank
@@ Property / cites work @@
+A new proof of Szemerédi's theorem
@@ Property / cites work: A new proof of Szemerédi's theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002760
@@ Property / cites work: Q3002760 / rank @@
+Normal rank
@@ Property / cites work @@
+Simple analysis of graph tests for linearity and PCP
+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 @@
+Conditional hardness for satisfiable 3-CSPs
@@ Property / cites work: Conditional hardness for satisfiable 3-CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+Testing Basic Boolean Formulae
@@ Property / cites work: Testing Basic Boolean Formulae / rank @@
+Normal rank
@@ Property / cites work @@
+A Parallel Repetition Theorem
@@ Property / cites work: A Parallel Repetition Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549650
@@ Property / cites work: Q3549650 / rank @@
+Normal rank
@@ Property / cites work @@
+A PCP characterization of NP with optimal amortized query complexity
+Normal rank
@@ Property / cites work @@
+Gowers Uniformity, Influence of Variables, and PCPs
+Normal rank
@@ Property / cites work @@
+Q4542548
@@ Property / cites work: Q4542548 / rank @@
+Normal rank