Circuit Complexity Courses and Certifications

Association for Computing Machinery (ACM)

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Explore circuit lower bounds and derandomization, focusing on AC circuits, algorithmic methods, and pseudorandom generators. Learn about recent developments in average-case circuit analysis.

• YouTube
• 21 minutes
• On-Demand
• Free Online Course

Simons Institute

Top-Down Lower Bounds for Depth-Four Circuits

Explores new proof techniques for depth-4 boolean circuit complexity, applying robust sunflowers and block unpredictability to demonstrate exponential lower bounds for the parity function.

• YouTube
• 1 hour 1 minute
• On-Demand
• Free Online Course

Simons Institute

Recent Structure Lemmas for Depth-Two Threshold Circuits

Explore recent advancements in structure lemmas for depth-two threshold circuits, focusing on Boolean devices and their implications in computational complexity theory.

• YouTube
• 28 minutes
• On-Demand
• Free Online Course

IIT Hyderabad;  NPTEL

Computational Complexity

Explore computational complexity theory, models of computation, and complexity classes. Learn about time, space, randomness, and other aspects of computation in this advanced computer science course.

• Swayam
• 12 weeks
• On-Demand
• Free Online Course

Ryan O'Donnell

Quantum Complexity - Quantum Computation at CMU

Explore quantum complexity, error probabilities, and complexity classes in this advanced lecture on quantum computation and information theory.

• YouTube
• 1 hour 23 minutes
• On-Demand
• Free Online Course

Institute for Advanced Study

Proof and Circuit Complexity - Robert Robere

Explore proof and circuit complexity with Robert Robere, delving into Boolean circuits, monotone circuits, slice functions, and the Click function to understand computational limitations.

• YouTube
• 24 minutes
• On-Demand
• Free Online Course

IEEE

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Explore lifting techniques in circuit and proof complexity, focusing on Cutting Planes measures, communication complexity, and applications to monotone circuits and formulas.

• YouTube
• 21 minutes
• On-Demand
• Conference Talk

IEEE

Tight Quantum Time-Space Tradeoffs for Function Inversion

Explore quantum time-space tradeoffs for function inversion, examining classical tradeoffs, circuit complexity, and a generic framework. Delve into proof overviews and multi-instance gains.

• YouTube
• 26 minutes
• On-Demand
• Conference Talk

IEEE

The Constant Depth Formula and Partial Function Versions of MCSP are Hard

Explore the complexity of MCSP variants, including partial function and constant depth formula versions, and their implications for circuit lower bounds and computational hardness.

• YouTube
• 23 minutes
• On-Demand
• Conference Talk

Association for Computing Machinery (ACM)

Optimizing Semi-Honest Secure Multiparty Computation for the Internet

Optimizing secure multiparty computation for internet use, focusing on efficiency improvements in BMR protocol and OT-based methods for honest-minority settings.

• YouTube
• 27 minutes
• On-Demand
• Conference Talk

Simons Institute

Logic and Probabilistic Circuits - Lecture 4

Explore advanced concepts in logic and probabilistic circuits, focusing on their applications in database theory and artificial intelligence.

• YouTube
• 1 hour 1 minute
• On-Demand
• Free Online Course

Simons Institute

Logic and Probabilistic Circuits - Part 3

Explore advanced concepts in logic and probabilistic circuits, focusing on their applications in database theory and AI algorithms.

• YouTube
• 1 hour
• On-Demand
• Free Online Course

IEEE

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

Explore groundbreaking research on circuit complexity theory, focusing on the connection between derandomization techniques and establishing lower bounds for circuit sizes across various computational models.

• YouTube
• 24 minutes
• On-Demand
• Free Online Course

IEEE

Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

Explore the complexity theory concept of non-deterministic quasi-polynomial time and its average-case hardness for ACC circuits in this advanced computer science presentation.

• YouTube
• 20 minutes
• On-Demand
• Free Online Course

Paul G. Allen School

Innovations in Theoretical Computer Science 2020 - Session 10

Explores cutting-edge research in theoretical computer science, covering topics like computational hardness, random strings, decision trees, and pseudorandomness. Features presentations from leading experts in the field.

• YouTube
• 1 hour 29 minutes
• On-Demand
• Free Online Course