Swiss Winter School on Theoretical Computer Science

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

Slides of Lecture 1.
Slides of Lecture 2.
Slides of Lecture 3.
Slides of Lecture 4.


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

Slides of Raghu's lectures.


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.

Slides of Amir's lectures.

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


9.02.20

18:30 Registration and badge pickup
19:30 Welcome reception

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 Leisure time and discussions
17:00 – 18:30 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 Leisure time and discussions
17:00 – 18:30 Lecture (Kasper Green Larsen)

12.02.20

08:30 – 10:00 Lecture (Kasper Green Larsen)
10:00 – 10:30 Coffee break
10:30 – 12:00 Lecture (Amir Shpilka)
12:00 – 17:00 Leisure time 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 Leisure time and discussions

14.02.20

08:30 – 10:00 Lecture (Amir Shpilka)
10:00 – 10:30 Coffee break
10:30 – 12:00 Lecture (Raghu Meka)
12:00 – 12:30 Concluding remarks

Organizers

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 (shared rooms) and board (breakfast and dinner).

Getting to Zinal

The Swiss Winter School on Lower Bounds and Communication Complexity will be held at the Hotel Europe, 3961 Zinal, Switzerland.

Please note that the last bus connecting Sierre to Zinal on Sunday, February 9th leaves Sierre at 19:40.

Directions to Zinal (Val d'Anniviers)

By public transportation

From Lausanne (approx. 2 h 30 min)

  • Take train IR 90 from Lausanne to Sierre
  • Get off at Sierre station and take the underground passage or the footbridge to the bus stop, on the other side of the tracks
  • Take bus 451 to Vissoie
  • In Vissoie, take bus 453 to Zinal
  • Get off at the `Zinal, centre' stop

    • (Type `Lausanne' to `Zinal' on the SBB timetable page to reserve the entire trip)

From Geneva airport (approx. 3 h 20 min)

  • Take train IR 90 toward Lausanne and Sierre
  • Get off at Sierre station and take the underground passage or the footbridge to the bus stop, on the other side of the tracks
  • Take bus 451 to Vissoie
  • In Vissoie, take bus 453 to Zinal
  • Get off at the `Zinal, centre' stop

    • (Type `Geneva Airport' to `Zinal' on the SBB timetable page to reserve the entire trip)

From Zürich (approx. 4 h)

  • Take the train from Zürich Hauptbahnhof to Sierre (1 train change in Brig or Visp)
  • Get off at Sierre station and take the underground passage or the footbridge to the bus stop, on the other side of the tracks
  • Take bus 451 to Vissoie
  • In Vissoie, take bus 453 to Zinal
  • Get off at the `Zinal, centre' stop

    • (Type `Zürich' to `Zinal' on the SBB timetable page to reserve the entire trip)

From Zürich airport (approx. 4 h)

  • Take the train from Zürich airport to Sierre (1 train change in Brig or Visp)
  • Get off at Sierre station and take the underground passage or the footbridge to the bus stop, on the other side of the tracks
  • Take bus 451 to Vissoie
  • In Vissoie, take bus 453 to Zinal
  • Get off at the `Zinal, centre' stop

    • (Type `Zürich Airport' to `Zinal' on the SBB timetable page to reserve the entire trip)

By car

From Lausanne (approx. 1 h 45 min)

  • Take the A9 motorway toward Sierre
  • Take exit 29-Sierre-est toward Sierre-est/Salgesch/Val d'Anniviers
  • At the roundabout, take the 2nd exit to Val d?Anniviers
  • When you get to Vissoie, on `Place des cars', follow signs to Zinal

From Geneva airport (approx. 2 h 20 min)

  • Take the A1 motorway toward Lausanne
  • Continue onto A9 toward Sierre
  • Take exit 29-Sierre-est toward Sierre-est/Salgesch/Val d'Anniviers
  • At the roundabout, take the 2nd exit to Val d'Anniviers
  • When you get to Vissoie, on `Place des cars', follow signs to Zinal

From Zürich or Zürich airport (approx. 3 h 30 min)

  • Take the A1 motorway toward Bern/Vevey
  • In Vevey, switch to the A9 toward Sierre
  • Take exit 29-Sierre-est toward Sierre-est/Salgesch/Val d'Anniviers
  • At the roundabout, take the 2nd exit to Val d'Anniviers
  • When you get to Vissoie, on `Place des cars', follow signs to Zinal
or
  • Take the A1 motorway followed by the car transport by rail (Kandersteg-Goppenstein) via the Lötschberg tunnel to Sierre
  • In Sierre, at the roundabout, take the 2nd exit to Val d'Anniviers
  • When you get to Vissoie, on `Place des cars', follow signs to Zinal