Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Local Proofs Approaching the Witness Length
event speaker icon
Noga Ron-Zewi (Haifa University)
event date icon
Wednesday, 27.11.2019, 12:30
event location icon
Taub 201 Taub Bld.
Interactive oracle proofs are a hybrid between interactive proofsand probabilistically-checkable proofs, where the prover is allowed to interactwith a verifier by sending relatively long messages to the verifier, who inturn is only allowed to query a few of the bits that were sent.

In this work we construct, for any NP relation for whichmembership can be decided in polynomial-time and bounded polynomial space (e.g.,SAT, Hamiltonicity, Clique, Vertex-Cover, etc.), interactive oracle proofs inwhich the proof length approaches the witness length. The number of rounds, aswell as the number of queries made by the verifier, are constant. Our proofleverages recent constructions of high-rate locally testable tensor codes. Inparticular, we bypass the barrier imposed by the low rate of multiplicationcodes (e.g., Reed-Solomon, Reed-Muller or AG codes) - a core component in priorconstructions.

Joint work with Ron Rothblum.