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.
Overview
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
-
Circuit Complexity Theory
-
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
-
Circuit Lower Bounds from Algorithm Design - An Overview I
-
Composition Theorems via Lifting
-
Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory - Robert Robere
-
Top-Down Lower Bounds for Depth-Four Circuits
