Efficient and High Soundness Constructions in Different Proof Systems (PCP, IOP and IP of proximity)


Event details

Date 18.06.2024
Hour 10:0012:00
Speaker Yuxi Zheng
Category Conferences - Seminars
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Dimitar Jetchev

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

2. Interactive Proofs of Proximity: Delegating Computation in Sublinear Time
Guy Rothblum, Salil Vadhan, Avi Widgerson

3. Interactive Oracle Proofs with Constant Rate and Query Complexity
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner


Practical information

  • General public
  • Free


EDIC candidacy exam