Главная
Study mode:
on
1
Intro
2
(Oversimplified) History and Motivation
3
(Oversimplified) History: Part 2
4
Subsequent Developments
5
Black-box and White-box Derandomization
6
Alternative Plan for Average-case?
7
Difficulties with previous approaches
8
Circuit Lower Bounds and Derandomization
9
Derandomizing Merlin-Arthur yields Average-Case Circuit Lower Bounds
10
Bootstrapping of Derandomization to NPRG
11
Partial Solution: Conditional A.E. MA
12
Adaptation to the Average-Case
13
Conditional Construction of NPRG: Adapted
14
The Key Issue on Improving C.'19 The Updated Question
Description:
Explore a computer science seminar on strong average-case circuit lower bounds derived from non-trivial derandomization. Delve into the history and motivation behind this topic, examining subsequent developments in black-box and white-box derandomization. Investigate the connection between circuit lower bounds and derandomization, learning how derandomizing Merlin-Arthur protocols yields average-case circuit lower bounds. Analyze the bootstrapping of derandomization to NPRG and examine conditional constructions. Gain insights into the key issues in improving previous results and understand the updated questions in this field of computational complexity theory.

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen

Institute for Advanced Study
Add to list
0:00 / 0:00