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
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- A Zero Knowledge Sumcheck and its Applicationsarxiv.org
- What's new | Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Taoterrytao.wordpress.com
- small-sumcheck.pdfpeople.cs.georgetown.edu
- COMP 598 Fall 2020 - Proof Complexitycs.mcgill.ca
- Proofs, beliefs and algorithms through the lens of Sum of Squaressumofsquares.org
- P versus NP problem - Wikipediaen.wikipedia.org
- A Time-Space Tradeoff for the Sumcheck Provereprint.iacr.org
- 370.pdfeprint.iacr.org
- WHIR: Reed–Solomon Proximity Testing with Super-Fast Verificationeprint.iacr.org
- Quantum Lovasz Local Lemmaarxiv.org