Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Circuit complexity

Related courses (22)

MATH-683: Fine-grained and parameterized complexity

The classical distinction between polynomial time solvable and NP-hard problems is often too coarse. This course covers techniques for proving more fine-grained lower and upper bounds on complexity of computational problems. ...

CS-602: Foundation of probabilistic proofs

Probabilistic proof system (eg PCPs and IPs) have had a tremendous impact on the theoretical computer science, and have also found practical uses. They underlie delegation of computation protocols and hardness of approximation. This course covers the found ...