The Taub Faculty of Computer Science Events and Talks

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.