YoVDO

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

Offered By: Institute for Advanced Study via YouTube

Tags

Complexity Theory Courses Computer Science Courses Discrete Mathematics Courses Derandomization Courses

Course Description

Overview

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.

Syllabus

Intro
(Oversimplified) History and Motivation
(Oversimplified) History: Part 2
Subsequent Developments
Black-box and White-box Derandomization
Alternative Plan for Average-case?
Difficulties with previous approaches
Circuit Lower Bounds and Derandomization
Derandomizing Merlin-Arthur yields Average-Case Circuit Lower Bounds
Bootstrapping of Derandomization to NPRG
Partial Solution: Conditional A.E. MA
Adaptation to the Average-Case
Conditional Construction of NPRG: Adapted
The Key Issue on Improving C.'19 The Updated Question


Taught by

Institute for Advanced Study

Related Courses

Probabilistic Graphical Models 1: Representation
Stanford University via Coursera
Computer Security
Stanford University via Coursera
Intro to Computer Science
University of Virginia via Udacity
Introduction to Logic
Stanford University via Coursera
Internet History, Technology, and Security
University of Michigan via Coursera