Computer Science/Discrete Mathematics Seminar II

The lifeblood of interactive proof systems is randomness, without which interaction becomes redundant. Thus, a natural long-standing question is which types of proof systems can indeed be derandomized and collapsed to a single-message NP-type protocol. Classical results tell us that, under strong circuit lower bounds, we can do so for proof systems with constantly many rounds of interaction, while incurring a polynomial time overhead (i.e., the deterministic verifier is polynomially slower than the original verifier in the proof system).

We will see how derandomization of such proof systems can be achieved with optimal time overhead, under strong hardness assumptions. Moreover, we'll show that we can even do so with essentially no time overhead at all, if one is willing to compromise on obtaining a system that is secure only against inputs and proofs that can be found efficiently. Along the way, we will introduce a new and natural model of computation, namly argument systems that are secure "on average".

As a corollary, under strong but plausible assumptions, there exists an argument system for #SAT in which the verifier runs in time $2^{εn}$, where $ε >0$ may be arbitrarily small, and is secure against adversaries running in exponential time $2^{O(n)}$. (A common conjecture is that there doesn't exist a verifier with such running time that is secure against all-powerful adversaries.)

The talk is based on a joint work with Lijie Chen.