Explore a conference talk delving into strong average-case circuit lower bounds derived from non-trivial derandomization. Gain insights into circuit lower bounds, AC circuits, and circuit analysis problems. Discover the algorithmic method and subsequent developments in the field. Examine the concept of derandomization, including pseudorandom generators fooling AC[2]. Learn about the work on strong average-case circuit lower bounds for ACC, including hardness amplification attempts, circuit analysis of approximate sum, and the final proof. Conclude with an overview of new developments in this area of computational complexity theory.
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Intro
Motivation 1: Circuit Lower Bounds
AC circuits
AC [6] circuits
Circuit Analysis Problems
Algorithmic Method
Subsequent Developments
Motivation 2: Derandomization
Pseudorandom Generators Fooling AC [2]?
This Work: Strong Average-Case Circuit Lower Bounds for ACC
First Attempt: Hardness Amplification
Still, Step I...?
Circuit Analysis of Approximate Sum
Hardness Amplification via Approximate Sum
The Final Proof
New Developments
Taught by
Association for Computing Machinery (ACM)
Related Courses
-
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
-
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization
-
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds
-
Derandomization from Algebraic Hardness - Treading the Borders
-
Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits
-
Circuit Lower Bounds from Algorithm Design - An Overview I
