Swiss Winter School on Theoretical Computer Science

10-14 February 2020

Overview

The Swiss Winter School on Lower Bounds and Communication Complexity is the first in a series of annual winter schools in Theoretical Computer Science jointly organized by EPFL and ETH Zurich. The goal of the school is to educate top international theory PhD students about exciting recent developments in the field. The winter school will be held in Zinal, a mountain village in the Swiss Alps that has a long tradition of hosting academic workshops. This allows for nice excursions and stimulating discussions in a relaxed atmosphere.

Speakers


Kasper Green Larsen (born 1986) is an Associate Professor at the Department of Computer Science at Aarhus University, Denmark. Kasper received his Ph.D. from Aarhus University in 2013. He is a member of the Young Academy under the Royal Danish Academy of Sciences and Letters. Kasper is also a recipient of the Presburger Award 2019 and has received best paper awards at CRYPTO and STOC, as well as best student paper awards at STOC and FOCS. His research interests spans several areas of theoretical computer science, with a particular focus on lower bounds techniques and data structures.is an Associate Professor at the Department of Computer Science at Aarhus University. His research span in many areas of theoretical computer science, but in particular, he enjoys working on data structures, range searching, lower bounds, dimensionality reduction, and streaming algorithms. Kasper received his Ph. D. from Aarhus University in 2013 and since 2017 he has been a member of the Young Academy under the Royal Danish Academy of Sciences and Letters.

Raghu Meka is an Associate Professor in the CS department at UCLA. He is broadly interested in complexity theory, learning and probability theory. He got his PhD at UT Austin under the (wise) guidance of David Zuckerman. After that, he spent two years in Princeton as a postdoctoral fellow at the Institute for Advanced Study with Avi Wigderson, and at DIMACS, at Rutgers. And after that, he spent an enjoyable year as a researcher at the Microsoft Research Silicon Valley Lab.

Amir Shpilka is a Professor at the Blavatnik School of Computer Science at Tel-Aviv University. Prior to joining Tel-Aviv University he was an associate professor with the Faculty of Computer Science at the Technion-Israel Institute of Technology. He obtained his Ph.D. at the Hebrew university, where he was advised by Avi Wigderson.

Courses

Data Structure Lower Bounds (Kasper Green Larsen)
Proving strong unconditional lower bounds on the time needed to solve computational problems is a holy grail in theoretical computer science. This is unfortunately a notoriously difficult task, and we still have no techniques for proving super linear lower bounds for general (arbitrary depth) circuits or similar computational models. One of the few areas where we have been quite successful in proving time lower bounds, is in data structures. The field of data structures is concerned with how efficiently one can represent a data set under various queries and updates to the data. In this series of lectures, we will cover the most central techniques that have been developed for proving data structure lower bounds. Along the way, we will also discuss the limitations of the techniques and current barriers we face in proving stronger data structure lower bounds.


Communication Complexity (Raghu Meka)
Communication complexity studies the minimal amount of communication required for computing a function when the input is distributed between multiple parties. Since its introduction by Yao, communication complexity has become a central area within theoretical computer science with a plethora of applications that include circuit lower bounds, streaming lower bounds, mathematical optimization, cryptography. The goal of the lectures is to present a broad introduction to the area focusing on the central techniques in the area leading up to some notable results from the last few years (e.g., lifting theorems, extension complexity).


Algebraic complexity - a quick intro (Amir Shpilka)
Algebraic complexity studies the complexity of computing algebraic problems such as computing the determinant or permanent of a matrix, multiplying two matrices etc., using the basic arithmetic operations. In this series of talks we will give a quick overview of the field starting from the basic definitions and hopefully reaching the ideas behind state of the art lower bounds. We will also discuss the connection to the more standard boolean complexity classes and argue that the best place to start attacking the P vs. NP problem is the algebraic world.

Reading material: There is an excellent survey by Ramprasad Saptharishi on the basic structural results and all known lower bounds. Another survey is by Amir Yehudayoff and myself. It covers fewer lower bounds but contains a wider overview of the field.


Program (Tentative)


10.02.20

08:30 – 10:00 Lecture (Raghu Meka)
10:00 – 10:30 Coffee break
10:30 – 12:00 Lecture (Amir Shpilka)
12:00 – 17:00 Sports and discussions
17:00 – 19:00 Lecture (Kasper Green Larsen)

11.02.20

08:30 – 10:00 Lecture (Raghu Meka)
10:00 – 10:30 Coffee break
10:30 – 12:00 Lecture (Amir Shpilka)
12:00 – 17:00 Sports and discussions
17:00 – 19:00 Lecture (Kasper Green Larsen)

12.02.20

08:30 – 10:00 Lecture (Raghu Meka)
10:00 – 10:30 Coffee break
10:30 – 12:00 Lecture (Amir Shpilka)
12:00 – 17:00 Sports and discussions
17:00 – 19:00 Poster session

13.02.20

08:30 – 10:00 Lecture (Kasper Green Larsen)
10:00 – 10:30 Coffee break
10:30 – 12:00 Lecture (Raghu Meka)
12:00 – 17:00 Sports and discussions
17:00 – 19:00 Poster session

14.02.20

08:30 – 10:00 Lecture (Amir Shpilka)
10:00 – 10:30 Coffee break
10:30 – 12:00 Lecture (Kasper Green Larsen)
12:00 – 12:30 Concluding remarks

How to apply

To apply, please click the button below and fill out the form. The application deadline is November 15th 2019. Acceptance/rejection notifications will be sent by December 1st 2019. Attendance of the winter school is free of charge and includes room and board (shared rooms).