Probabilistic checking of proofs
From MaRDI portal
Publication:3841041
DOI10.1145/273865.273901zbMath0903.68076OpenAlexW2019578639WikidataQ55869216 ScholiaQ55869216MaRDI QIDQ3841041
Publication date: 25 October 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1998-45/
Related Items (only showing first 100 items - show all)
Subquadratic SNARGs in the random oracle model ⋮ Quantum de Finetti theorems under local measurements with applications ⋮ Algebraic testing and weight distributions of codes. ⋮ Towards optimal lower bounds for clique and chromatic number. ⋮ On regularity of Max-CSPs and Min-CSPs ⋮ On the approximability of clique and related maximization problems ⋮ Bounds on 2-query locally testable codes with affine tests ⋮ Fast approximate probabilistically checkable proofs ⋮ Quantum information and the PCP theorem ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Succinct non-interactive arguments via linear interactive proofs ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries ⋮ Column subset selection problem is UG-hard ⋮ Sparse approximation is provably hard under coherent dictionaries ⋮ An algebraic proof of the real number PCP theorem ⋮ Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ A PCP theorem for interactive proofs and applications ⋮ Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier ⋮ Testing juntas ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ On locally decodable codes, self-correctable codes, and \(t\)-private PIR ⋮ Succinct arguments in the quantum random oracle model ⋮ Linear-size constant-query IOPs for delegating computation ⋮ Low-degree test with polynomially small error ⋮ Refereed delegation of computation ⋮ Strong Inapproximability of the Shortest Reset Word ⋮ An Algebraic Proof of the Real Number PCP Theorem ⋮ QMA with Subset State Witnesses ⋮ Committee polyhedral separability: complexity and polynomial approximation ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ On the hardness of learning intersections of two halfspaces ⋮ Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete ⋮ Non-black-box simulation in the fully concurrent setting, revisited ⋮ Exponential inapproximability of selecting a maximum volume sub-matrix ⋮ Quantum multi-prover interactive proof systems with limited prior entanglement. ⋮ QMA with Subset State Witnesses ⋮ The hunting of the SNARK ⋮ 2-transitivity is insufficient for local testability ⋮ More on average case vs approximation complexity ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Tight security bounds for Micali's SNARGs ⋮ Derandomized parallel repetition via structured PCPs ⋮ Max NP-completeness made easy ⋮ PCP characterizations of NP: toward a polynomially-small error-probability ⋮ Finding large 3-free sets. I. The small \(n\) case ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ Combinatorial PCPs with efficient verifiers ⋮ Shorter arithmetization of nondeterministic computations ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Improved approximation algorithms for projection games ⋮ Approximating maximum independent sets by excluding subgraphs ⋮ Vertex cover might be hard to approximate to within \(2 - \varepsilon \) ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ Best-order streaming model ⋮ Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ On the severity of Braess's paradox: designing networks for selfish users is hard ⋮ Components in time-varying graphs ⋮ The Chinese deliveryman problem ⋮ Testing low-degree polynomials over prime fields ⋮ Smooth and strong PCPs ⋮ Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ Efficient approximation of the metric CVRP in spaces of fixed doubling dimension ⋮ Three-Player Entangled XOR Games are NP-Hard to Approximate ⋮ Satisfying Degree-d Equations over GF[2 n] ⋮ Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs ⋮ On Sums of Locally Testable Affine Invariant Properties ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs ⋮ Short Locally Testable Codes and Proofs ⋮ Bravely, Moderately: A Common Theme in Four Recent Works ⋮ Randomness and Computation ⋮ Almost Transparent Short Proofs for NPℝ ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Quantum XOR Games ⋮ Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly ⋮ Characterizations of locally testable linear- and affine-invariant families ⋮ Probably bounded suboptimal heuristic search ⋮ Cryptography with constant input locality ⋮ Spot-checkers ⋮ Interactive and probabilistic proof-checking ⋮ APX-hardness of domination problems in circle graphs ⋮ Testing algebraic geometric codes ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems ⋮ What can be efficiently reduced to the Kolmogorov-random strings? ⋮ Spartan: efficient and general-purpose zkSNARKs without trusted setup ⋮ Rank-one quantum games ⋮ The PCP theorem for NP over the reals ⋮ A PCP of proximity for real algebraic polynomials ⋮ PSPACE has constant-round quantum interactive proof systems ⋮ Combinatorial PCPs with short proofs
This page was built for publication: Probabilistic checking of proofs
