PCPs via the low-degree long code and hardness for constrained hypergraph coloring (Q891178): Difference between revisions

@@ Property / cites work @@
+Q3002852
@@ Property / cites work: Q3002852 / rank @@
+Normal rank
@@ Property / cites work @@
+Making the Long Code Shorter
@@ Property / cites work: Making the Long Code Shorter / rank @@
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Efficient probabilistic checkable proofs and applications to approximation
+Normal rank
@@ Property / cites work @@
+Optimal Testing of Reed-Muller Codes
@@ Property / cites work: Optimal Testing of Reed-Muller Codes / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of equality constraint languages
@@ Property / cites work: The complexity of equality constraint languages / rank @@
+Normal rank
@@ Property / cites work @@
+PCP characterizations of NP: toward a polynomially-small error-probability
+Normal rank
@@ Property / cites work @@
+PCPs via the low-degree long code and hardness for constrained hypergraph coloring
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+The hardness of 3-uniform hypergraph coloring
@@ Property / cites work: The hardness of 3-uniform hypergraph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
+Normal rank
@@ Property / cites work @@
+Hardness of Approximate Hypergraph Coloring
@@ Property / cites work: Hardness of Approximate Hypergraph Coloring / rank @@
+Normal rank
@@ Property / cites work @@
+On the NP-Hardness of Max-Not-2
@@ Property / cites work: On the NP-Hardness of Max-Not-2 / rank @@
+Normal rank
@@ Property / cites work @@
+A PRG for lipschitz functions of polynomials with applications to sparsest cut
+Normal rank
@@ Property / cites work @@
+Hardness results for approximate hypergraph coloring
+Normal rank
@@ Property / cites work @@
+Noise stability of functions with low influences: invariance and optimality
+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 @@
+Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
+Normal rank
@@ Property / cites work @@
+Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
+Normal rank
@@ Property / cites work @@
+The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
+Normal rank