Efficient and High Soundness Constructions in Different Proof Systems (PCP, IOP and IP of proximity)
Event details
| Date | 18.06.2024 |
| Hour | 10:00 › 12:00 |
| Speaker | Yuxi Zheng |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Dimitar Jetchev
Abstract
This research proposal investigates the construction of three different proof systemsâProbabilistically Checkable Proofs (PCP), Interactive Proofs (IP), and Interactive Oracle Proofs (IOP)âthrough testing and coding techniques. Key topics include Fourier analysis of property tests, the role of proximity proofs, and interactive proof compositions. The surveyed papers address critical questions in theoretical computer science, such as PCPâs implications for hardness of approximation results, possibility of constructing proofs with linear proof length and constant query complexity, and explores practical applications in delegation of computation, all of which motivates further exploration in this domain.
Background papers
1.Some Optimal Inapproximability Results, Johan Håstad
https://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf
2. Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
Guy Rothblum, Salil Vadhan, Avi Widgerson
https://privacytools.seas.harvard.edu/files/privacytools/files/stoc283fp-rothblum.pdf
3. Interactive Oracle Proofs with Constant Rate and Query Complexity
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
https://eprint.iacr.org/2016/324.pdf
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Dimitar Jetchev
Abstract
This research proposal investigates the construction of three different proof systemsâProbabilistically Checkable Proofs (PCP), Interactive Proofs (IP), and Interactive Oracle Proofs (IOP)âthrough testing and coding techniques. Key topics include Fourier analysis of property tests, the role of proximity proofs, and interactive proof compositions. The surveyed papers address critical questions in theoretical computer science, such as PCPâs implications for hardness of approximation results, possibility of constructing proofs with linear proof length and constant query complexity, and explores practical applications in delegation of computation, all of which motivates further exploration in this domain.
Background papers
1.Some Optimal Inapproximability Results, Johan Håstad
https://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf
2. Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
Guy Rothblum, Salil Vadhan, Avi Widgerson
https://privacytools.seas.harvard.edu/files/privacytools/files/stoc283fp-rothblum.pdf
3. Interactive Oracle Proofs with Constant Rate and Query Complexity
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner
https://eprint.iacr.org/2016/324.pdf
Practical information
- General public
- Free