We thank all participants for this successful event!
Complexity theory traditionally tries to classify problems into polynomial-time solvable or NP-hard. For huge amounts of data, however, already cubic or even quadratic running time might be intractable. Can we distinguish linear-, quadratic-, and cubic-time problems using negative criteria analogous to NP-hardness?
"Fine-grained complexity" yields such criteria in the form of "conditional lower bounds" obtained via reductions from certain hard core problems like Satisfiability, All Pairs Shortest Paths, or 3SUM. Beyond distinguishing linear, quadratic, and cubic time, this approach can be generalized to study diverse aspects of computation such as approximability, nondeterministic complexity, derandomization, etc. -- for problems in P as well as for NP-complete problems.
The goal of this summer school is to give a broad overview of this emerging subfield at the intersection of complexity theory and algorithm design. The topics range from conditional lower bounds for polynomial-time problems, through the foundations of the Strong Exponential Time Hypothesis for Satisfiability, to applications in dynamic graph algorithms. This summer school's scope is international, and its goal is to bring together leading researchers with international participants of graduate level and above.
No prior knowledge in fine-grained complexity is necessary to attend this course.
ADFOCS is organized by Karl Bringmann, Marvin Künnemann, and Cosmina Croitoru as part of the activities of the Algorithms and Complexity Group and the International Max Planck Research School of the Max Planck Institute for Informatics.
Please do not hesitate to contact us for any questions via email to adfocs@mpi-inf.mpg.de.
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.
August 13 Monday |
August 14 Tuesday |
August 15 Wednesday |
August 16 Thursday |
August 17 Friday |
|
---|---|---|---|---|---|
8.00-8.55 | Registration (Campus E1 4, ground floor) |
||||
9.00 | Lecture Ramamohan Paturi |
Lecture Danupon Nanongkai |
Lecture Karl Bringmann |
Lecture Danupon Nanongkai |
Lecture Ramamohan Paturi |
10.45 | Coffee Break | Coffee Break | Coffee Break | Coffee Break | Coffee Break |
11.15 | Exercises Ramamohan Paturi |
Exercises Danupon Nanongkai |
Talks by MPII members |
Exercises Danupon Nanongkai |
Lecture Danupon Nanongkai |
13.00 | Lunch | Lunch | Lunch | Lunch | Lunch |
14.30 | Lecture Karl Bringmann |
Lecture Ramamohan Paturi |
Excursion (bus leaves at 13.30) |
Lecture Karl Bringmann |
|
16.15 | Coffee Break | Coffee Break | Coffee Break | ||
16.45-18.30 | Exercises Karl Bringmann |
Exercises Ramamohan Paturi |
Exercises Karl Bringmann |
On Wednesday morning, members of the Algorithms and Complexity Group (D1) at MPI-Inf will introduce the group by presenting their own work:
On Wednesday afternoon, we offer as an excursion a tour on bicycle handcars.
The registration fee is EUR 130 for early registration
(deadline July 08, 2018) and EUR 180 for late registration (after July 09, 2018).
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.
Websites of previous ADFOCS summer schools.
We will offer a limited number of travel grants for graduate students and young researchers.
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.
June 17, 2018, Central European Summer Time
(By the deadline, we must receive both the CV and the letter of recommendation)
June 27, 2018
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:
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 there are still train connections.
From the train station to your hotel you can use public transport: Buses and a tramway that is called "Saarbahn".
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).
Your ADFOCS name badge entitles you to free public transport in Saarbrücken from August 13 to August 17. 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).
Lectures:
Exercises:
Lectures:
Exercises:
Further material: Slides and exercises of a course taught at Saarland University (Summer 2016)
Lectures:
Exercises:
(Always up-to-date versions can be found on Dropbox)