Main Lectures

Course 1. Algorithms and lower bounds.

Lecturer: Ryan Williams (MIT)

Course 2. Hardness of Approximation.

Lecturer: Luca Trevisan (Bocconi University)

Course 3. Higher-Order Complexity

Lecturer: Bruce Kapron (U. of Victoria)

Computational complexity theory has developed significantly over the past fifty years, providing an understanding of the limits of efficient computation. Traditionally, complexity theory considers computation over discrete and finitary inputs. On the other hand, many computational problems arise in settings where inputs are naturally viewed as infinitary or even continuous. While computability theory has a long history of considering such models, complexity theory in this setting is much less developed. In these lectures I will survey some of the work that has been done toward developing complexity theory for higher-order computation, and consider applications in areas such as logic, computable analysis, programming languages, and ordinary complexity theory.

Course 4. Parametrized Complexity.

Lecturer: Daniel Marx (Max Planck Institute)

Focussed Lectures 

Course A. Quantum Verification and Complexity

Lecturer: Elham Kashefi (CNRS & Sorbonne University)

Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification, has been highlighted as a significant challenge on the road to scalable quantum computing technology. We review the most significant approaches to quantum verification and compare them in terms of structure, complexity and required resources.

Course B. Static Complexity Analysis.

Lecturer: Georg Moser (U. of Innsbruck)

Course C. Complexity Theory for Black-Box Optimization Heuristics.

Lecturer: Carola Doerr (CNRS & Sorbonne University) 

Many real-world optimization challenges are not explicitly modeled as optimization problems, but only allow to evaluate the quality of different alternatives through physical experiments or computer simulations. Parameter tuning, clinical studies, and many engineering tasks are prime example for such black-box optimization problems. The hardness of black-box problems can be assessed by counting the evaluations needed to obtain an optimal solution (or, depending on the context, a solution that meets some other quality requirements).

In this lecture we motivate the study of black-box complexity, survey a few basic models, and demonstrate how black-box complexity has impacted the design of black-box optimization techniques. We will also discuss connections to recreational Mathematics, including coin weighing games, Mastermind, etc. Several open problems will be mentioned during this lecture. None of them requires prior knowledge in black-box optimization.