MPI-INF Logo
Adfocs
ADFOCS 2017

18th Max Planck Advanced Course on the Foundations of Computer Science

18th Max Planck Advanced Course

on the Foundations of Computer Science

August 21 - 25, 2017, Saarbrücken, Germany

Algebraic Complexity Theory and Computer Algebra

Computational complexity theory tries to understand the inherent hardness of computational problems. Its two complementing facets are finding faster algorithms (upper bounds) and proving hardness results (lower bounds). In this edition of ADFOCS, we will be looking at these two facets of computation in an algebraic setting: Computer algebra and algebraic complexity theory. We aim at giving overviews in different topics, ranging from matrix multiplication to algebraic circuits. The algebraic perspective will reveal the rich mathematical structure of the objects and questions which we will study.

This summer school's scope is international, and its goal is to bring together leading researchers with international participants of graduate level and above.

Markus Bläser

Markus Bläser

Saarland University

Valiant's framework of algebraic complexity theory, determinant vs permanent

François Le Gall

François Le Gall

Kyoto University

Complexity of Matrix Multiplication
and Bilinear Problems:
Algorithms and Applications

Amir Yehudayoff

Amir Yehudayoff

Technion - Israel Institute of Technology

Algebraic Circuit Complexity:
depth reductions, Shallow Circuits,
Monotone devices, Multilinearity

Joachim von zur Gathen We have to announce the sad news that due to health problems Prof. Dr. Joachim von zur Gathen will not be able to join us this year. We wish him all the very best and a quick and full recovery.

ADFOCS is organized by Christian Ikenmeyer and Michael Sagraloff as a part of the activities of the Algorithms and Complexity Group and the International Max Planck Research School of the Max Planck Institute for Informatics.

Contact

Please do not hesitate to contact us for any questions via email to adfocs@mpi-inf.mpg.de.

Program

This year's ADFOCS features three lecturers, each of which will give three lectures and two exercise sessions. They will be distributed to eight blocks of about four hours. A typical morning or afternoon block will start with 1 1/2 hours of lecture, followed by 2 hours of exercises (in small groups without the lecturers). During the exercise periods, the respective lecturer will be around, as well as some fruits, snacks, and drinks.
All the lectures will take place in Lecture Hall 001 in Campus E1 3, and all the exercises will take place in the Room 024 in Campus E1 4.

The excursion is on Wednesday.

There will be an additional slot for the members of the Algorithms and Complexity Group (D1) at MPI to introduce the different research areas of the group.

Schedule

August 21
Monday
August 22
Tuesday
August 23
Wednesday
August 24
Thursday
August 25
Friday
8.00-8.55 Registration
(Campus E1 4, ground floor)
9.00 Lecture
Amir Yehudayoff
Lecture
François Le Gall
Lecture
Amir Yehudayoff
Lecture
François Le Gall
Lecture
Amir Yehudayoff
10.45 Coffee Break Coffee Break Coffee Break Coffee Break Coffee Break
11.15 Exercises
Amir Yehudayoff
Exercises
François Le Gall
Lecture
François Le Gall
Exercises
François Le Gall
Talks by members of MPII
13.00 Lunch Lunch Lunch Lunch Lunch
14.30 Lecture
Markus Bläser
Lecture
Markus Bläser
Excursion
(Starts at 14:00)
Lecture
Markus Bläser
16.15 Coffee Break Coffee Break Coffee Break
16.45-18.30 Exercises
Markus Bläser
Exercises
Markus Bläser
Exercises
Amir Yehudayoff

Talks by members of MPI-INF

On Friday morning, some members of MPI-INF will present their own work

Excursion

On Wednesday afternoon, there will be an excursion offered. The excursion destination would be an adventure park.

Registration

The registration fee is EUR 130 for early registration (deadline: July 15, 2017, Central European Summer Time) and EUR 180 for late registration (July 16 onward).
This fee covers course material, lunches, and the excursion; it does not cover hotel accommodation.
We will provide some grants for graduate students and young researchers.
If you are a student (including PhD student) please register here: student registration
Otherwise please register here: regular registration

Grants

We will offer a limited number of travel grants for graduate students and young researchers.

Application

If you wish to apply for a grant, please send an email with a brief CV (name, affiliation, complete address, education, publications, nationality, etc.);
Please have your supervisor at your institute send an email with a brief letter of recommendation, certifying in particular your relation with the topics in ADFOCS, before the deadline.

Note that the travel grant is meant to roughly cover your local expenses (hotel/youth hostel, registration); it will not be sufficient to cover flight costs!

Please send both emails to adfocs@mpi-inf.mpg.de and indicate as subject "ADFOCS grant application". You will receive a confirmation of receipt of your application.

Deadline

June 23, 2017, Central European Summer Time
(By the deadline, we must receive both the CV and the letter of recommendation)

Notification

July 7, 2017

Accommodation

The participants are responsible for their accommodation. In Saarbrücken per-night prices including taxes and breakfast typically range from EURO 20 (youth hostel, double room) to about 70 Euro (hotel, single room).

We have reserved a certain number of rooms in the following hotels. Please note that these reservation expire:

When booking a room at these hotels, please refer to "ADFOCS" since we have negotiated special rates for you.

Further options (without reserved contingents) include:

Travel information

ADFOCS 2017 takes place at the campus of Saarland University, in the building of Max Planck Institut for Informatics (MPII) and the Computer Science Building.

Traveling to Saarbrücken

You will probably try to reach Saarbrücken by train. If you have a flight to Frankfurt, this is extremely easy. There is a train station right in the terminal building. Trains run frequently. You have to buy a ticket before you board the train, and there you can also ask which trains to take.

If you are a group of people, note that there is a special offer called "Schönes-Wochenende-Ticket" (nice week-end ticket) for sundays and saturdays. It costs 44 Euros (or 42 at the machines) and entitles up to 5 people to travel a whole day on all local trains ("S-Bahn" (S), "Regional-Express" (RE), "Regional-Bahn" (RB)). Several such connections to Saarbrücken only use such trains, so this is not a real limitation. For week days, there is a similar offer called "Quer-durchs-Land"-Ticket.

If you arrive at some other airport, things are not that simple, but still easy. From Frankfurt-Hahn, served by Ryanair and other cheap airlines, there is a quite regular bus-service. From Stuttgart, Cologne or Dortmund you would also take the train, but this might take a good three to four hours.

From Saarbrücken main train station ("Saarbrücken Hauptbahnhof") to your hotel

From the train station to your hotel you can use public transport: Buses and a tramway that is called "Saarbahn".

  • The Hotel B&B Saarbrücken is located directly at the main train station.
  • For Hotel Madeleine, you take the tramway S1 with destination "Sarreguemines", "Brebach", or "Kleinblittersdorf" and get off at the stop "Johanneskirche" (two stops). You can also walk (15 minutes).
  • For Hotel Weller, you take bus 124 with destination "Universität Busterminal" and get off at the stop "An der Trift" (five stops).
  • For the Youth Hostel, you take bus 124 with destination "Universität Busterminal" and get off at the stop "Prinzenweiher/DJH" (six stops). On Sunday, bus 124 does not operate. You can travel either to Ilseplatz by Bus 102 (11th stop), and walk from there (about 7 minutes), or you may check other options here: www.saarbahn.de (von: Saarbrücken Hbf, nach: Saarbrücken, Europa Jugendherberge).
  • For Hotel Kaiserhof, take the tramway S1 with destination "Sarreguemines", "Brebach", or "Kleinblittersdorf" and get off at the stop "Uhlandstrasse" (five stops).
  • For the Etap-Hotel, take the tramway S1 with destination "Sarreguemines", "Brebach", or "Kleinblittersdorf" and get off at the stop "Kieselhumes". (six stops).

Specific bus queries (using the names of the bus/tram stops) can be entered here (enter the name of the origin bus/tram stop in the "von" field, the destination in the "nach" field, and in the next two, date and time).

Getting to the MPII and back

Your ADFOCS name badge entitles you to free public transport in Saarbrücken from August 21 to August 25. All buses to the MPII will have "Universität" as part of their destination sign. You get off the bus at the stop "Universität Mensa". The MPI building is located on the left side a bit further down the street (Building number E1.4). You can also look at the map below. On the way back you depart from the same bus stop (other side of the road).

  • From the main train station and from Hotel B&B Saarbrücken, take bus 124 with destination "Universität Busterminal" and get off at the stop "Universität Mensa (12 stops). On the way back, the destination is "Betriebsbahnhof".
  • From the city center (Hotel Madeleine is located here) several buses to the MPII (stop "Universität Mensa") start at the bus stop "Rathaus": bus 101 with destination "Dudweiler Dudoplatz" (10 stops), bus 102 with destination "Dudweiler Dudoplatz" (13 stops), bus 109 with destination "Universität Busterminal " (13 stops), and bus 150 with destination "Neuweiler Sternplatz" (10 stops). On the way back to the city center you get off the bus at the bus stop "Johanneskirche". The destinations are "Füllengarten Siedlung" for bus 101, "Altenkessel Talstrasse" for bus 102, "Saarcenter/Goldene Bremm" for bus 109, and "Saarcenter" for bus 150.
  • From the Hotel Kaiserhof (tramway stop "Uhlandstrasse") or the Etap-Hotel (tramway stop "Kieselhumes") take the tramway S1 back in direction main station (destinations "Siedlerheim" and "Riegelsberg Süd") and get off at the tramway stop "Johanneskirche" (three/four stops). Walk over to the bus stop "Rathaus" and proceed as above.
  • From Hotel Weller (bus stop "An der Trift") or the Youth Hostel (bus stop "Prinzenweiher/DJH"), you enter the bus at the same stop you left when coming from the train station and go on to "Universität Mensa" taking bus 101 with destination "Dudweiler Dudoplatz", bus 124 with destination "Universität Busterminal", or bus 150 with destination "Neuweiler Sternplatz" (seven/six stops). On the way back, the destinations are "Füllengarten Siedlung" (bus 101), "Betriebsbahnhof" (bus 124), and "Saarcenter" (bus 150).

Campus map
  • Markus Bläser

    Markus Bläser

    Saarland University

    Valiant's framework of algebraic complexity theory, determinant vs permanent

  • François Le Gall

    François Le Gall

    Kyoto University

    Complexity of Matrix Multiplication and Bilinear problems: Algorithms and Applications

  • Amir Yehudayoff

    Amir Yehudayoff

    Technion - Israel Institute of Technology

    Algebraic Circuit Complexity: depth reductions, Shallow Circuits,
    Monotone devices, Multilinearity

  • Joachim von zur Gathen
    We have to announce the sad news that due to health problems Prof. Dr. Joachim von zur Gathen will not be able to join us this year. We wish him all the very best and a quick and full recovery.