Simple PCPs with poly-log rate and query complexity
From MaRDI portal
Recommendations
- Short PCPs with Polylog Query Complexity
- Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
- A PCP characterization of NP with optimal amortized query complexity
- Simultaneous (poly-time, log-space) lower bounds
- Query complexity and the polynomial Freiman-Ruzsa conjecture
- Query efficient PCPs with perfect completeness
- Toward a deterministic polynomial time algorithm with optimal additive query complexity
- Toward a deterministic polynomial time algorithm with optimal additive query complexity
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Small PCPs with low query complexity
Cited in
(23)- New direct-product testers and \(2\)-query PCPs
- Robust PSPs of proximity, shorter PSPs and applications to coding
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- Combinatorial PCPs with short proofs
- On Dinur’s proof of the PCP theorem
- Simultaneous (poly-time, log-space) lower bounds
- On the vector subspaces of \(\mathbb{F}_{2^n}\) over which the multiplicative inverse function sums to zero
- Constant rate PCPs for circuit-SAT with sublinear query complexity
- A combinatorial characterization of smooth LTCs and applications
- scientific article; zbMATH DE number 1688375 (Why is no real title available?)
- Spartan: efficient and general-purpose zkSNARKs without trusted setup
- Symmetric LDPC codes and local testing
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- On the locally testable code of Dinur \textit{et al.} (2021)
- Testing algebraic geometric codes
- Shorter arithmetization of nondeterministic computations
- Short PCPs with Polylog Query Complexity
- Small PCPs with low query complexity
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Probabilistically checkable proofs and codes
- Symmetric LDPC codes and local testing
- Bravely, moderately: a common theme in four recent works
- Dense locally testable codes cannot have constant rate and distance
This page was built for publication: Simple PCPs with poly-log rate and query complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581427)
