YoVDO

Proof and Circuit Complexity - Robert Robere

Offered By: Institute for Advanced Study via YouTube

Tags

Theoretical Computer Science Courses Circuit Complexity Courses Boolean Circuits Courses

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 Theory
Indian 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