Derandomized parallel repetition via structured PCPs (Q645129): Difference between revisions

@@ 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.1007/s00037-011-0013-5
+Normal rank
@@ Property / OpenAlex ID @@
+W2146392217
@@ Property / OpenAlex ID: W2146392217 / 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 @@
+Improved low-degree testing and its applications
@@ Property / cites work: Improved low-degree testing and its applications / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient probabilistically checkable proofs and applications to approximations
+Normal rank
@@ Property / cites work @@
+Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
+Normal rank
@@ Property / cites work @@
+Sound 3-Query PCPPs Are Long
@@ Property / cites work: Sound 3-Query PCPPs Are Long / rank @@
+Normal rank
@@ Property / cites work @@
+Q4313087
@@ Property / cites work: Q4313087 / rank @@
+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 @@
+PCP characterizations of NP: toward a polynomially-small error-probability
+Normal rank
@@ Property / cites work @@
+Clustering in the Boolean Hypercube in a List Decoding Regime
+Normal rank
@@ Property / cites work @@
+Composition of Low-Error 2-Query PCPs Using Decodable PCPs
+Normal rank
@@ Property / cites work @@
+Derandomized parallel repetition via structured PCPs
+Normal rank
@@ Property / cites work @@
+Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
+Normal rank
@@ Property / cites work @@
+Interactive proofs and the hardness of approximating cliques
+Normal rank
@@ Property / cites work @@
+Q4234094
@@ Property / cites work: Q4234094 / rank @@
+Normal rank
@@ Property / cites work @@
+A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
+Normal rank
@@ Property / cites work @@
+Q5302082
@@ Property / cites work: Q5302082 / rank @@
+Normal rank
@@ Property / cites work @@
+New direct-product testers and 2-query PCPs
@@ Property / cites work: New direct-product testers and 2-query PCPs / rank @@
+Normal rank
@@ Property / cites work @@
+Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
+Normal rank
@@ Property / cites work @@
+Q4002466
@@ Property / cites work: Q4002466 / rank @@
+Normal rank
@@ Property / cites work @@
+Ramanujan graphs
@@ Property / cites work: Ramanujan graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial PCPs with Efficient Verifiers
@@ Property / cites work: Combinatorial PCPs with Efficient Verifiers / rank @@
+Normal rank
@@ Property / cites work @@
+Sub-Constant Error Low Degree Test of Almost-Linear Size
+Normal rank
@@ Property / cites work @@
+Optimization, approximation, and complexity classes
+Normal rank
@@ Property / cites work @@
+Nearly-linear size holographic proofs
@@ Property / cites work: Nearly-linear size holographic proofs / rank @@
+Normal rank
@@ Property / cites work @@
+A Parallel Repetition Theorem
@@ Property / cites work: A Parallel Repetition Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Q4527015
@@ Property / cites work: Q4527015 / rank @@
+Normal rank