On the public citation graph

Small PCPs with low query complexity

https://doi.org/10.1007/pl00001606
0 signed · 63 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-48523-6_64openalex-snapshot
Many-Valued Logics and Holographic Proofs
inferredcites →https://doi.org/10.1007/bf01200056openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01200430openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf02392825openalex-snapshot
Clique is hard to approximate within n1−ε
inferredcites →https://doi.org/10.1016/0020-0190(88)90152-4openalex-snapshot
Short propositional formulas represent nondeterministic computations
inferredcites →https://doi.org/10.1016/0304-3975(94)90251-8openalex-snapshot
On the power of multi-prover interactive protocols
inferredcites →https://doi.org/10.1016/c2013-0-08299-0openalex-snapshot
Introduction to Parallel Algorithms and Architectures
inferredcites →https://doi.org/10.1109/fscs.1990.89518openalex-snapshot
Algebraic methods for interactive proof systems
inferredcites →https://doi.org/10.1109/istcs.1995.377032openalex-snapshot
Some improvements to total degree tests
inferredcites →https://doi.org/10.1109/sfcs.1991.185342openalex-snapshot
Fully parallelized multi prover protocols for NEXP-time
inferredcites →https://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferredcites →https://doi.org/10.1109/sfcs.1992.267824openalex-snapshot
Probabilistic checking of proofs; a new characterization of NP
inferredcites →https://doi.org/10.1109/sfcs.1995.492573openalex-snapshot
Free bits, PCPs and non-approximability-towards tight results
inferredcites →https://doi.org/10.1137/0218012openalex-snapshot
The Knowledge Complexity of Interactive Proof Systems
inferredcites →https://doi.org/10.1137/s0097539793255151openalex-snapshot
Robust Characterizations of Polynomials with Applications to Program Testing
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
inferredcites →https://doi.org/10.1137/s0097539796302531openalex-snapshot
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
inferredcites →https://doi.org/10.1145/103418.103428openalex-snapshot
Checking computations in polylogarithmic time
inferredcites →https://doi.org/10.1145/129712.129783openalex-snapshot
Two-prover one-round proof systems
inferredcites →https://doi.org/10.1145/146585.146605openalex-snapshot
Algebraic methods for interactive proof systems
inferredcites →https://doi.org/10.1145/167088.167174openalex-snapshot
Efficient probabilistically checkable proofs and applications to approximations
inferredcites →https://doi.org/10.1145/195058.195129openalex-snapshot
Improved non-approximability results
inferredcites →https://doi.org/10.1145/195058.195132openalex-snapshot
Nearly-linear size holographic proofs
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/225058.225181openalex-snapshot
A parallel repetition theorem
inferredcites →https://doi.org/10.1145/225058.225183openalex-snapshot
Impossibility results for recycling random bits in two-prover proof systems
inferredcites →https://doi.org/10.1145/226643.226652openalex-snapshot
Interactive proofs and the hardness of approximating cliques
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/258533.258641openalex-snapshot
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
inferredcites →https://doi.org/10.1145/258533.258642openalex-snapshot
Improved low-degree testing and its applications
inferredcites →https://doi.org/10.1145/273865.273901openalex-snapshot
Probabilistic checking of proofs
inferredcites →https://doi.org/10.1145/278298.278306openalex-snapshot
Proof verification and the hardness of approximation problems
inferredcites →https://doi.org/10.1145/301250.301265openalex-snapshot
PCP characterizations of NP
inferredcites →https://doi.org/10.1145/322217.322225openalex-snapshot
Fast Probabilistic Algorithms for Verification of Polynomial Identities
inferredcites →https://doi.org/10.1145/3335741.3335758openalex-snapshot
Multi-prover interactive proofs: how to remove intractability assumptions
inferredcites →https://doi.org/10.1145/62212.62223openalex-snapshot
Multi-prover interactive proofs: how to remove intractability
inferredcites →https://doi.org/10.48550/arxiv.1307.3975openalex-snapshot
Some Improvements to Total Degree Tests

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/9781118600207.ch13openalex-snapshot
Inapproximability of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1002/9781119005353.biblioopenalex-snapshot
General Bibliography
inferred← citeshttps://doi.org/10.1002/9781119005353.ch13openalex-snapshot
Inapproximability of Combinatorial Optimization Problems
inferred← citeshttps://doi.org/10.1007/3-540-44693-1openalex-snapshot
STACS 2001
inferred← citeshttps://doi.org/10.1007/978-3-030-36033-7_19openalex-snapshot
Linear-Size Constant-Query IOPs for Delegating Computation
inferred← citeshttps://doi.org/10.1007/978-3-319-56617-7_19openalex-snapshot
Computational Integrity with a Public Random String from Quasi-Linear PCPs
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_6openalex-snapshot
Short Locally Testable Codes and Proofs: A Survey in Two Parts
inferred← citeshttps://doi.org/10.1007/978-3-642-36594-2_18openalex-snapshot
Succinct Non-interactive Arguments via Linear Interactive Proofs
inferred← citeshttps://doi.org/10.1007/978-3-662-49099-0_2openalex-snapshot
Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs
inferred← citeshttps://doi.org/10.1007/978-3-662-53644-5_2openalex-snapshot
Interactive Oracle Proofs
inferred← citeshttps://doi.org/10.1007/s00145-022-09424-4openalex-snapshot
Succinct Non-Interactive Arguments via Linear Interactive Proofs
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.07.030openalex-snapshot
Shorter arithmetization of nondeterministic computations
inferred← citeshttps://doi.org/10.1109/ccc.2005.27openalex-snapshot
Short PCPs Verifiable in Polylogarithmic Time
inferred← citeshttps://doi.org/10.1109/focs.2004.59openalex-snapshot
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique
inferred← citeshttps://doi.org/10.1109/focs.2013.42openalex-snapshot
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181878openalex-snapshot
Locally testable codes and PCPs of almost-linear length
inferred← citeshttps://doi.org/10.1137/050646445openalex-snapshot
Short PCPs with Polylog Query Complexity
inferred← citeshttps://doi.org/10.1137/s0097539705446810openalex-snapshot
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
inferred← citeshttps://doi.org/10.1137/s0097539705447037openalex-snapshot
Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
inferred← citeshttps://doi.org/10.1145/1162349.1162351openalex-snapshot
Locally testable codes and PCPs of almost-linear length
inferred← citeshttps://doi.org/10.1145/1595391.1595394openalex-snapshot
Sound 3-Query PCPPs Are Long
inferred← citeshttps://doi.org/10.1145/2422436.2422481openalex-snapshot
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
inferred← citeshttps://doi.org/10.1145/2488608.2488681openalex-snapshot
On the concrete efficiency of probabilistically-checkable proofs
inferred← citeshttps://doi.org/10.1145/2901294openalex-snapshot
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
inferred← citeshttps://doi.org/10.1145/780542.780631openalex-snapshot
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2018.58openalex-snapshot
Erasures vs. Errors in Local Decoding and Property Testing
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.