Ron Rothblum: Local Proofs Approaching the Witness Length

Speaker: Ron Rothblum

Date: Friday, April 02, 2021

Time: 1:00 PM to 2:30 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: email dlehto@mit.edu for zoom link

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan and Yael Kalai

Contact: Deborah Goodwin, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu, crypto@lists.csail.mit.edu

Reminder Subject: TALK: Ron Rothblum: Local Proofs Approaching the Witness Length

Abstract:

Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP, the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent (like in a PCP). IOPs have become a central tool for the construction of efficient proof-systems.

For any NP relation for which membership can be decided in polynomial-time and bounded polynomial space (e.g., SAT, Hamiltonicity, Clique, Vertex-Cover, etc.) and for any constant \gamma>0, we construct an IOP with communication complexity (1+\gamma) \cdot n, where n is the original witness length. The number of rounds as well as the number of queries made by the IOP verifier are constant.

Joint work with Noga Ron-Zewi

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2021.

Created by Deborah Goodwin at Wednesday, March 31, 2021 at 3:25 PM.