Short Locally Testable Codes and Proofs: A Survey in Two Parts (Q4933364): 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/978-3-642-16367-8_6
+Normal rank
@@ Property / OpenAlex ID @@
+W189554415
@@ Property / OpenAlex ID: W189554415 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Upper bound on the communication complexity of private information retrieval
+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 @@
+Non-deterministic exponential time has two-prover interactive protocols
+Normal rank
@@ Property / cites work @@
+Q4252728
@@ Property / cites work: Q4252728 / rank @@
+Normal rank
@@ Property / cites work @@
+Free Bits, PCPs, and Nonapproximability---Towards Tight Results
+Normal rank
@@ Property / cites work @@
+Efficient probabilistically checkable proofs and applications to approximations
+Normal rank
@@ Property / cites work @@
+Improved non-approximability results
@@ Property / cites work: Improved non-approximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
+Normal rank
@@ Property / cites work @@
+Locally Testable Codes Require Redundant Testers
@@ Property / cites work: Locally Testable Codes Require Redundant Testers / rank @@
+Normal rank
@@ Property / cites work @@
+Some 3CNF properties are hard to test
@@ Property / cites work: Some 3CNF properties are hard to test / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
+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 @@
+Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
+Normal rank
@@ Property / cites work @@
+Self-testing/correcting with applications to numerical problems
+Normal rank
@@ Property / cites work @@
+Q4542539
@@ Property / cites work: Q4542539 / rank @@
+Normal rank
@@ Property / cites work @@
+Private information retrieval
@@ Property / cites work: Private information retrieval / 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 @@
+Composition of Low-Error 2-Query PCPs Using Decodable PCPs
+Normal rank
@@ Property / cites work @@
+Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
+Normal rank
@@ Property / cites work @@
+-query locally decodable codes of subexponential length
+Normal rank
@@ Property / cites work @@
+Fast approximate PCPs
@@ Property / cites work: Fast approximate PCPs / rank @@
+Normal rank
@@ Property / cites work @@
+Interactive proofs and the hardness of approximating cliques
+Normal rank
@@ Property / cites work @@
+Q5682225
@@ Property / cites work: Q5682225 / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of multi-prover interactive protocols
+Normal rank
@@ Property / cites work @@
+Short Locally Testable Codes and Proofs
@@ Property / cites work: Short Locally Testable Codes and Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Property testing and its connection to learning and approximation
+Normal rank
@@ Property / cites work @@
+Lower bounds for linear locally decodable codes and private information retrieval
+Normal rank
@@ Property / cites work @@
+Locally testable codes and PCPs of almost-linear length
+Normal rank
@@ Property / cites work @@
+Small PCPs with low query complexity
@@ Property / cites work: Small PCPs with low query complexity / rank @@
+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 @@
+On the efficiency of local decoding procedures for error-correcting codes
+Normal rank
@@ Property / cites work @@
+Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
+Normal rank
@@ Property / cites work @@
+Exponential lower bound for 2-query locally decodable codes via a quantum argument
+Normal rank
@@ Property / cites work @@
+Fully parallelized multi-prover protocols for NEXP-time
+Normal rank
@@ Property / cites work @@
+Algebraic methods for interactive proof systems
@@ Property / cites work: Algebraic methods for interactive proof systems / rank @@
+Normal rank
@@ Property / cites work @@
+Combinatorial Construction of Locally Testable Codes
+Normal rank
@@ Property / cites work @@
+Combinatorial PCPs with Efficient Verifiers
@@ Property / cites work: Combinatorial PCPs with Efficient Verifiers / rank @@
+Normal rank
@@ Property / cites work @@
+Computationally Sound Proofs
@@ Property / cites work: Computationally Sound Proofs / rank @@
+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 @@
+Robust Characterizations of Polynomials with Applications to Program Testing
+Normal rank
@@ Property / cites work @@
+Q4938652
@@ Property / cites work: Q4938652 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549622
@@ Property / cites work: Q3549622 / rank @@
+Normal rank