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

Concept

Polynomial hierarchy

Related courses (6)

CS-214: Software construction

Learn how to design and implement reliable, maintainable, and efficient software using a mix of programming skills (declarative style, higher-order functions, inductive types, parallelism) and fundamental software construction concepts (reusability, abstr ...

MATH-458: Programming concepts in scientific computing

The aim of this course is to provide the background in scientific computing. The class includes a brief introduction to basic programming in c++, it then focuses on object-oriented programming and c++ specific programming techniques. Typical class hierarch ...

MATH-483: Gödel and recursivity

Gödel incompleteness theorems and mathematical foundations of computer science ...

COM-501: Advanced cryptography

This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it presents some techniques to validate the security of crypt ...

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. ...

MATH-632: Semidefinite Optimization and Applications to Geometric and Combinatorial Problems

This course covers the following topics: Introduction to conic optimization, Duality in conic programming, Sums of squares/ SemideFinite relaxation for independence number and chromatic number, Harmonic analysis on [owe, sets, Lasserre's hierarchy, Packing ...