Linear Pcps
Probabilistically checkable proofs whose verifier may only query linear functions of the proof, including the fully linear and one-query cases.
| Status | Problem | Tags |
|---|---|---|
|
DPP Field Size The small-field regime is settled: soundness \(\Theta(1/\sqrt{q})\) is achieved and proved optimal. In the large-field regime the source achieves soundness \(\varepsilon\) for every prime \(p\) at least \(\tilde{\Omega}(S^9/\varepsilon^6)\) and states in as many words that it believes the \(S\)-dependence is not tight. 4 open |
Linear PcpsSnarkstight-boundadaptation (ai) |
No matching items