Shorter arithmetization of nondeterministic computations (Q496013): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2015.07.030
+Normal rank
@@ Property / OpenAlex ID @@
+W935592923
@@ Property / OpenAlex ID: W935592923 / rank @@
+Normal rank
@@ Property / cites work @@
+Network information flow
@@ Property / cites work: Network information flow / rank @@
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Q4527016
@@ Property / cites work: Q4527016 / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic checking of proofs
@@ Property / cites work: Probabilistic checking of proofs / rank @@
+Normal rank
@@ Property / cites work @@
+SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
+Normal rank
@@ Property / cites work @@
+Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+On the concrete efficiency of probabilistically-checkable proofs
+Normal rank
@@ Property / cites work @@
+Succinct Non-interactive Arguments via Linear Interactive Proofs
+Normal rank
@@ Property / cites work @@
+Q5513488
@@ Property / cites work: Q5513488 / rank @@
+Normal rank
@@ Property / cites work @@
+Arithmetization: A new method in structural complexity theory
+Normal rank
@@ Property / cites work @@
+Robust pcps of proximity, shorter pcps and applications to coding
+Normal rank
@@ Property / cites work @@
+Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
+Normal rank
@@ Property / cites work @@
+Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
+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 @@
+Q4133134
@@ Property / cites work: Q4133134 / rank @@
+Normal rank
@@ Property / cites work @@
+Composition of Low-Error 2-Query PCPs Using Decodable PCPs
+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 @@
+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 @@
+Q4527018
@@ Property / cites work: Q4527018 / rank @@
+Normal rank
@@ Property / cites work @@
+Interactive proof systems and alternating time-space complexity
+Normal rank
@@ Property / cites work @@
+Quadratic Span Programs and Succinct NIZKs without PCPs
+Normal rank
@@ Property / cites work @@
+Short Pairing-Based Non-interactive Zero-Knowledge Arguments
+Normal rank
@@ Property / cites work @@
+Q3826533
@@ Property / cites work: Q3826533 / rank @@
+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 @@
+Q4002466
@@ Property / cites work: Q4002466 / rank @@
+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 @@
+Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
+Normal rank
@@ Property / cites work @@
+Q5690468
@@ Property / cites work: Q5690468 / 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 @@
+Combinatorial PCPs with short proofs
@@ Property / cites work: Combinatorial PCPs with short proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
+Normal rank
@@ Property / cites work @@
+Two-query PCP with subconstant error
@@ Property / cites work: Two-query PCP with subconstant error / rank @@
+Normal rank
@@ Property / cites work @@
+Q5608026
@@ Property / cites work: Q5608026 / rank @@
+Normal rank
@@ Property / cites work @@
+On a Class of Rearrangeable Switching Networks Part I: Control Algorithm
+Normal rank
@@ Property / cites work @@
+Relations Among Complexity Measures
@@ Property / cites work: Relations Among Complexity Measures / rank @@
+Normal rank
@@ Property / cites work @@
+A New Lower Bound for the Number of Switches in Rearrangeable Networks
+Normal rank
@@ Property / cites work @@
+Nearly-linear size holographic proofs
@@ Property / cites work: Nearly-linear size holographic proofs / rank @@
+Normal rank
@@ Property / cites work @@
+On O(Tlog T) reduction from RAM computations to satisfiability
+Normal rank
@@ Property / cites work @@
+Robust Characterizations of Polynomials with Applications to Program Testing
+Normal rank
@@ Property / cites work @@
+Q4527015
@@ Property / cites work: Q4527015 / rank @@
+Normal rank
@@ Property / cites work @@
+Satisfiability Is Quasilinear Complete in NQL
@@ Property / cites work: Satisfiability Is Quasilinear Complete in NQL / rank @@
+Normal rank
@@ Property / cites work @@
+IP = PSPACE
@@ Property / cites work: IP = PSPACE / rank @@
+Normal rank
@@ Property / cites work @@
+IP = SPACE
@@ Property / cites work: IP = SPACE / rank @@
+Normal rank
@@ Property / cites work @@
+A Permutation Network
@@ Property / cites work: A Permutation Network / rank @@
+Normal rank