Главная
Study mode:
on
1
Intro
2
Motivation 1: Circuit Lower Bounds
3
AC circuits
4
AC [6] circuits
5
Circuit Analysis Problems
6
Algorithmic Method
7
Subsequent Developments
8
Motivation 2: Derandomization
9
Pseudorandom Generators Fooling AC [2]?
10
This Work: Strong Average-Case Circuit Lower Bounds for ACC
11
First Attempt: Hardness Amplification
12
Still, Step I...?
13
Circuit Analysis of Approximate Sum
14
Hardness Amplification via Approximate Sum
15
The Final Proof
16
New Developments
Description:
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)
Add to list
0:00 / 0:00