Explore a conference talk on derandomization techniques in computational complexity theory, focusing on the intersection of algebraic hardness and hitting set construction. Delve into the main theorem presented, its consequences for bootstrapping, and the novel generator described. Gain insights into lower bounds, algebraic circuits, and the reconstruction process for polynomials. Follow the speakers as they navigate the borders of current research in this field, offering a comprehensive overview of recent advancements and their implications for computational complexity theory.
Derandomization from Algebraic Hardness - Treading the Borders
Overview
Syllabus
Intro
Algebraic Circuits
Two Important Questions
Lower bounds and hitting sets
How are hitting sets constructed?
Generators from hardness
Main Theorem
Some consequences
Consequences for bootstrapping
The one trick that we use
Description of our generator
Proof overview
The univariate setting
Reconstruction of P
Reconstruction Step: Pictorially
No more fuss about the border
Improvements to bootstrapping
Conclusion
Taught by
IEEE FOCS: Foundations of Computer Science
