A&C Seminar: Roei Tell on "Hardness vs randomness without PRGs, and derandomizing interactive protocols without paying for it"
Speaker
Roei Tell
IAS
ABSTRACT:
Can we build a hardness to randomness framework that doesn't rely on classical pseudorandom generators (PRGs)? And can we remove randomness from interactive proof systems without paying for it in runtime overheads? This self-contained talk will follow up on Tuesday's colloquium talk, and will focus on two very recent results, from works with Lijie Chen.
First, we'll see how to deduce that BPP = P without classical PRGs, relying instead on non-black-box algorithmic techniques. This allows us to avoid assuming classical circuit lower bounds, and instead assume a new type of lower bounds for uniform probabilistic algorithms. We will show two-way connections between the promiseBPP = promiseP conjecture and this new type of lower bounds.
Secondly, we'll see how to transform every constant-round interactive protocol into a NP-type verifier that has essentially the same time complexity and that looks sound to any efficient adversary (under strong hardness assumptions). Consequently, for every eps>0, we conditionally construct a deterministic argument system for counting the number of satisfying assignments for an n-bit formula of size 2^{o(n)} in time 2^{eps*n}, with soundness against adversaries running in time 2^{O(n)}.
Can we build a hardness to randomness framework that doesn't rely on classical pseudorandom generators (PRGs)? And can we remove randomness from interactive proof systems without paying for it in runtime overheads? This self-contained talk will follow up on Tuesday's colloquium talk, and will focus on two very recent results, from works with Lijie Chen.
First, we'll see how to deduce that BPP = P without classical PRGs, relying instead on non-black-box algorithmic techniques. This allows us to avoid assuming classical circuit lower bounds, and instead assume a new type of lower bounds for uniform probabilistic algorithms. We will show two-way connections between the promiseBPP = promiseP conjecture and this new type of lower bounds.
Secondly, we'll see how to transform every constant-round interactive protocol into a NP-type verifier that has essentially the same time complexity and that looks sound to any efficient adversary (under strong hardness assumptions). Consequently, for every eps>0, we conditionally construct a deterministic argument system for counting the number of satisfying assignments for an n-bit formula of size 2^{o(n)} in time 2^{eps*n}, with soundness against adversaries running in time 2^{O(n)}.