18.408 F2022 Lectures 4–6: Quadratic Solvability, Low-degree Extensions and the Sum-check Protocol
ocw.mit.edu · 5,391 words · saved by 1 readers
N/A
18.408 Topics in Theoretical Computer Science Fall 2022 Lectures 4,5,6 Dor Minzer In this lecture we make the frst step in the proof of the PCP theorem, and establish seemingly strong inapproximability result for solving quadratic equations. This construction though will not be local at all (each one will involve all of the variables), and we will turn our attention into improving upon the locality of the construction. Towards this end, we will present the sum-check protocol and low-degree extensions. 1…
related reading
- 1404.5236 Sum-of-Squares Proofs and the Quest toward Optimal Algorithmsarxiv.org
- 370.pdfeprint.iacr.org
- 18.408 F2022 Lectures 2–3: Error Correcting Codesocw.mit.edu
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- The Spartan zkSNARK framework - Alin Tomescualinush.github.io
- dec9.pdfpeople.seas.harvard.edu
- nullstellensatzweb.math.princeton.edu
- Variants of KZG: Part III, Multilinear Commitments with Zeromorphblog.zksecurity.xyz
- SOS seminar lecture 1youtube.com
- unit-distance-proof.pdfcdn.openai.com
- small-sumcheck.pdfpeople.cs.georgetown.edu
- [2605.01192] Linear-Readout Floors and Threshold Recovery in Computation in Superpositionarxiv.org