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

Algebra & Algorithms
Moscow Institute of Physics and Technology via Coursera Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers - Toniann Pitassi
Institute for Advanced Study via YouTube Undergrad Complexity at CMU - SAT
Ryan O'Donnell via YouTube Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures
Association for Computing Machinery (ACM) via YouTube Wolverine - Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits
IEEE via YouTube