A&C Seminar: Roei Tell on "Hardness vs randomness without PRGs, and derandomizing interactive protocols without paying for it"

Speaker: Roei Tell , IAS

Date: Thursday, April 14, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Conference Room D451

Event Type: Seminar

Room Description:

Host:

Contact: Rahul Ilango, rilango@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: A&C Seminar: Roei Tell on "Hardness vs randomness without PRGs, and derandomizing interactive protocols without paying for it"

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)}.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar 2022.

Created by Rahul Ilango at Monday, April 11, 2022 at 4:11 PM.