Main Lectures

Course 1. Algorithms and lower bounds.

Lecturer: Ryan Williams (MIT)

Course 2. Hardness of Approximation.

Lecturer: Irit Dinur (The Weizmann Institute of Science)

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

Lecturer: TBA

Focussed Lectures 

Course A. Static Complexity Analysis.

Lecturer: Georg Moser (U. of Innsbruck)

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

Course A. TBA

Lecturer: TBA