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.

François Le Gall

François Le Gall

Kyoto University

Complexity of Matrix Multiplication
and Bilinear Problems:
Algorithms and Applications

Joachim von zur Gathen

Joachim von zur Gathen

Bonn-Aachen International Center for Information Technology

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

Amir Yehudayoff

Amir Yehudayoff

Technion - Israel Institute of Technology

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

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.

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 29
Monday
August 30
Tuesday
August 31
Wednesday
September 1
Thursday
September 2
Friday
8.00-8.55 Registration
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 Excursion Lunch Lunch
14.30 Lecture
Joachim von zur Gathen
Lecture
Joachim von zur Gathen
Lecture
Joachim von zur Gathen
16.15 Coffee Break Coffee Break Coffee Break
16.45-18.30 Exercises
Joachim von zur Gathen
Exercises
Joachim von zur Gathen
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.


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:

Materials

  • François Le Gall

    François Le Gall

    Kyoto University

    Complexity of Matrix Multiplication and Bilinear problems: Algorithms and Applications

  • Joachim von zur Gathen

    Joachim von zur Gathen

    Bonn-Aachen International Center for Information Technology

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

  • Amir Yehudayoff

    Amir Yehudayoff

    Technion - Israel Institute of Technology

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