Proof and Circuit Complexity - Robert Robere
Offered By: Institute for Advanced Study via YouTube
Course Description
Overview
Explore the fascinating world of proof and circuit complexity in this 24-minute talk by Robert Robere, a member of the School of Mathematics at the Institute for Advanced Study. Delve into topics such as Boolean circuits, restricted Boolean circuits, monotone circuits, slice functions, and click functions. Learn about the challenges in shrinking the gap between upper and lower bounds in circuit complexity theory. Gain insights from this concise yet informative presentation, which is part of a series of short talks by postdoctoral members at the Institute for Advanced Study.
Syllabus
Introduction
Boolean circuits
Restricted Boolean circuits
Monotone circuits
Slice functions
Click functions
Shrink the gap
Conclusion
Taught by
Institute for Advanced Study
Related Courses
Computational Complexity TheoryIndian Institute of Technology Kanpur via Swayam Computational Complexity
IIT Hyderabad via Swayam Quantum Complexity - Quantum Computation at CMU
Ryan O'Donnell via YouTube Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization
Association for Computing Machinery (ACM) via YouTube Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
IEEE via YouTube