- Lijie Chen Thesis Defense: ...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in August 2022
Lijie Chen Thesis Defense: Better Hardness via Algorithms, and New Forms of Hardness versus Randomness
Speaker:
Lijie Chen
Date: Wednesday, August 17, 2022
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: Kiva G449 / https://mit.zoom.us/j/98840757602
Event Type:
Room Description:
Host: Ryan Williams (Chair), Michael Sipser and Anand Natarajan
Contact: Deborah Goodwin, dlehto@csail.mit.edu
Relevant URL:
Speaker URL: None
Speaker Photo:
Reminders to:
seminars@csail.mit.edu, theory-seminars@csail.mit.edu, toc@csail.mit.edu
Reminder Subject:
TALK: Lijie Chen Thesis Defense: Better Hardness via Algorithms, and New Forms of Hardness versus Randomness
Abstract:
One central theme of complexity theory is the rich interplay between hardness (functions that are hard to compute) and pseudorandomness (procedures that convert randomized algorithms into equivalent deterministic algorithms). In one direction, from the classic works of Nisan-Wigderson and Impagliazzo-Wigderson, we know certain hardness hypothesis (circuit lower bounds) implies that all randomized algorithms can be "derandomized" with a polynomial overhead. In another direction, a decade ago, Williams proved that certain circuit lower bounds follow from non-trivial derandomization.
In this thesis we establish many new connections between hardness and pseudorandomness, strengthening and refining the classic works mentioned above.
(New circuit lower bounds from non-trivial derandomization.) Following Williams' algorithmic method, we prove several new circuit lower bounds using various non-trivial derandomization algorithms, including almost everywhere and strongly average-case lower bounds against ACC^0 circuits, and a new construction of rigid matrices.
(Super-fast and non-black-box derandomization from plausible hardness assumptions.) Under plausible hardness hypotheses, we obtain almost optimal worst-case derandomization of both randomized algorithms and constant-round Arthur-Merlin protocols. We also propose a new framework for non-black-box derandomization and demonstrate its usefulness by showing (1) it connects derandomization to a new type of hardness assumption against uniform algorithms and (2) (from plausible assumptions) it gives derandomization of both randomized algorithms and constant-round Arthur-Merlin protocols with almost no overhead such that no polynomial-time adversary can find a mistake.
Research Areas:
Impact Areas:
Created by Deborah Goodwin at Friday, August 05, 2022 at 4:25 PM.