Computer Science/Discrete Mathematics Seminar I

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send the k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication? This is the question of batch verification for NP statements.

In the talk, I will discuss recent progress on this question, showing different settings in which we can (and cannot) perform batch verification.