Small PCPs with low query complexity
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1688375
- Short PCPs with Polylog Query Complexity
- Simple PCPs with poly-log rate and query complexity
- Towards an optimal query efficient PCP?
- Query efficient PCPs with perfect completeness
- On the power of small-depth computation
- Short PCPs with projection queries
- Small complexity classes for computable analysis
- Small algorithms for small systems
- On the Computational Complexity of Small Descriptions
Cited in
(16)- scientific article; zbMATH DE number 7250164 (Why is no real title available?)
- Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
- Short locally testable codes and proofs: a survey in two parts
- Succinct non-interactive arguments via linear interactive proofs
- Sound 3-query PCPPs are long
- Interactive oracle proofs
- Quasi-linear size zero knowledge from linear-algebraic PCPs
- Simple PCPs with poly-log rate and query complexity
- Short locally testable codes and proofs
- Computational integrity with a public random string from quasi-linear PCPs
- Sub-constant error probabilistically checkable proof of almost-linear size
- scientific article; zbMATH DE number 1688375 (Why is no real title available?)
- Linear-size constant-query IOPs for delegating computation
- Shorter arithmetization of nondeterministic computations
- Sound 3-Query PCPPs Are Long
- scientific article; zbMATH DE number 1522925 (Why is no real title available?)
This page was built for publication: Small PCPs with low query complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946703)
