19th Max Planck Advanced Course

on the Foundations of Computer Science

August 13 - 17, 2018, Saarbrücken, Germany

Fine-Grained Complexity and Algorithms

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.

Ramamohan Paturi

University of California, San Diego

Foundations of Fine-grained Complexity

Danupon Nanongkai

KTH Royal Institute of Technology

Dynamic graphs: algorithms, conditional lower bounds, and complexity classes

Karl Bringmann

Max Planck Institute for Informatics

Hardness in P

ADFOCS is organized by Karl Bringmann, Marvin Künnemann and Cosmina Croitoru 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.

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.

Schedule

	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: tour on bicycle handcars	Lecture Karl Bringmann
16.15	Coffee Break	Coffee Break		Coffee Break
16.45-18.30	Exercises Karl Bringmann	Exercises Ramamohan Paturi		Exercises Karl Bringmann

Talks by members of MPI-INF

On Wednesday morning, members of the Algorithms and Complexity Group (D1) at MPI-Inf will introduce the group by presenting their own work.

Excursion

On Wednesday afternoon, we offer as an excursion a tour on bicycle handcars.

	August 13 Monday	August 14 Tuesday	August 15 Wednesday	August 16 Thursday	August 17 Friday
Complete menu:	Hot ragout of chicken with pasta and salad. Cauliflower soup and chocolate mousse	Salad of sausage stripes, roast potatoes, soup, ice cream	Mensa Closed: Pizza Catering	Hamburger pattie with brown sauce, potato-salad, vegetable soup, fruit	Steamed chicken-Breast, Sauce with peas, Rice, salad, Tomato-Soup and peach compote
Vegetarian Menu:	Risotto with mushrooms, coleslaw Maryland, creamcheese dessert with pineapple and coconut	Vegetarian spring roll, sweet & sour sauce, rice, salad, vanilla mousse		Potato gratin, salad, fruit yogurt	Yeast dumpling filled with plum jam and poppy seeds sprinkled on top, vanilla sauce, salad, tomato soup
Free flow:	Fish, balsamic lentils, mashed potatoes with horseradish	Egg plant with tomato sauce and bulgur with vegetables		Couscous with vegetables, tofu and nuts	Pasta with Tomato sauce and shrimps, salad
	Filled vegetarian peppers, tomato sauce, rice	Soja stripes asia like, chinese pasta		Soja escalope filled with peppers and tomatoes, salad	Falafel with sesame dip, salad
	Chili pot with lamb	Roast tuna with pasta		Lasagne Bolognese	Big escalope of pork with brown sauce, potato wedges
Salad buffett	Changes every day	Changes every day		Changes every day	Changes every day