On the public citation graph

Combinatorial PCPs with Short Proofs

0 signed · 40 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.1002/rsa.20120openalex-snapshot
Robust Locally Testable Codes and Products of Codes
inferredcites →https://doi.org/10.1007/11830924_29openalex-snapshot
Robust Local Testability of Tensor Products of LDPC Codes
inferredcites →https://doi.org/10.1007/3-540-08353-7_135openalex-snapshot
Graph-theoretic arguments in low-level complexity
inferredcites →https://doi.org/10.1007/3-540-48523-6_64openalex-snapshot
Many-Valued Logics and Holographic Proofs
inferredcites →https://doi.org/10.1007/978-3-642-03685-9_29openalex-snapshot
Composition of Semi-LTCs by Two-Wise Tensor Products
inferredcites →https://doi.org/10.1007/978-3-642-32512-0_55openalex-snapshot
A Combination of Testability and Decodability by Tensor Products
inferredcites →https://doi.org/10.1007/s00453-001-0078-7openalex-snapshot
Property Testing in Bounded Degree Graphs
inferredcites →https://doi.org/10.1016/0012-365x(92)90567-yopenalex-snapshot
On decoding by error location and dependent sets of error positions
inferredcites →https://doi.org/10.1016/0022-0000(91)90023-xopenalex-snapshot
Optimization, approximation, and complexity classes
inferredcites →https://doi.org/10.1016/s0924-6509(08)x7030-8openalex-snapshot
The Theory of Error-Correcting Codes
inferredcites →https://doi.org/10.1109/18.556667openalex-snapshot
Expander codes
inferredcites →https://doi.org/10.1109/ccc.2005.27openalex-snapshot
Short PCPs Verifiable in Polylogarithmic Time
inferredcites →https://doi.org/10.1109/ccc.2010.11openalex-snapshot
Derandomized Parallel Repetition of Structured PCPs
inferredcites →https://doi.org/10.1109/focs.2009.10openalex-snapshot
Combinatorial PCPs with Efficient Verifiers
inferredcites →https://doi.org/10.1109/focs.2013.42openalex-snapshot
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
inferredcites →https://doi.org/10.1137/050646445openalex-snapshot
Short PCPs with Polylog Query Complexity
inferredcites →https://doi.org/10.1137/110829660openalex-snapshot
IP = PSPACE Using Error-Correcting Codes
inferredcites →https://doi.org/10.1137/s0097539705446810openalex-snapshot
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
inferredcites →https://doi.org/10.1137/s0097539705446962openalex-snapshot
Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
inferredcites →https://doi.org/10.1137/s0097539797315744openalex-snapshot
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
inferredcites →https://doi.org/10.1145/103418.103428openalex-snapshot
Checking computations in polylogarithmic time
inferredcites →https://doi.org/10.1145/1132516.1132553openalex-snapshot
The PCP theorem by gap amplification
inferredcites →https://doi.org/10.1145/1162349.1162351openalex-snapshot
Locally testable codes and PCPs of almost-linear length
inferredcites →https://doi.org/10.1145/1595391.1595394openalex-snapshot
Sound 3-Query PCPPs Are Long
inferredcites →https://doi.org/10.1145/195058.195132openalex-snapshot
Nearly-linear size holographic proofs
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/322123.322138openalex-snapshot
Relations Among Complexity Measures
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.4086/toc.2009.v005a012openalex-snapshot

What points at this work

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

inferred← citeshttps://doi.org/10.1007/978-3-030-17653-2_4openalex-snapshot
Aurora: Transparent Succinct Arguments for R1CS
inferred← citeshttps://doi.org/10.1007/978-3-031-07085-3_10openalex-snapshot
Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier
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/s00037-014-0080-5openalex-snapshot
Combinatorial PCPs with Efficient Verifiers
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/focs.2013.42openalex-snapshot
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
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
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.