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)