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

Saarland University

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

François Le Gall

Kyoto University

Complexity of Matrix Multiplication
and Bilinear Problems:
Algorithms and Applications

Amir Yehudayoff

Technion - Israel Institute of Technology

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

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.

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 21 Monday	August 22 Tuesday	August 23 Wednesday	August 24 Thursday	August 25 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 Markus Bläser	Lecture Markus Bläser		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.

	August 21 Monday	August 22 Tuesday	August 23 Wednesday	August 24 Thursday	August 25 Friday
Full Meal:	Turkey strips, pasta, mixed cabbage salad, cream of leek soup, junket with cherries	breaded pork schnitzel, parsley potato, mixed vegetables, chicken noodle soup, fruit cocktail	turkey ragout, rice, zucchini salad, rich chicken soup, apple junket	fried beef and onions in gravy, french fries, vitamin-mix, eggshell noodle soup, fruit	breaded pollack fillet, herb remoulade, mashed potatoes, cucumber salad with dill, asparagus cream soup, junket with berries
Vegetarian Menu:	Chinese rice dish, lettuce, white salad dressing, vanilla pudding	Broccoli and potato casserole, endive potato salad, white salad dressing, fruit cocktail	macaroni, neapolitan sauce, shredded cheese, mixed salad, white salad dressing, pineapple-mandarins compote	Punjabi Rajma (Indian dish), rice Mexican salad, tagliatelle	rigatoni, champignon cream sauce, grated cheese, mixed raw vegetable salad, chocolate pudding
Free flow:	Chicken breast fillet, spinach-tomato sauce and ebly, apple Baked crusty fish filet, sauce Tirolinne, parsley potatoes or rice Potatoes (wedges), spicy chili sauce or garlic sauce Pasta buffet: Tomato bechamel sauce; spaghetti Milano, champignon cream sauce, curry sauce, pesto, Cappeletti Verdi, Rustico Verdura; veggie pasta squares, cheese tortellini, spaghetti, spinach pasta, olives and bell peppers Salad buffet: tomatos, white cabbage, cucumbers, onion rings, carrots, mixed sweet peper, corn, radicchio Mensacafe (Lunch) Ground Floor: leaf salad, white dressing; turkey steak, leaf salad, dressing; vegetable fritter; Bruesseler wafers with cream and hot cherries	Mediterranean chicken and rice skillet, almond romanesco atlantic breaded plaice, remoulade sauce lemon parsley potato, rice fair trade cheese Swabian noodles, carrot salad, cabbage salad pulled pork burger with coleslaw, ciabatta with feta, barbecue sauce, tomatoes, iceberg lettuce, cucumber, onion slices Salad bar: tomatoes, white cabbage cucumbers, onion slices, carrots, mixed sweet pepper corn, hot peperoni, lollo bianco, green lettuce, radiccio dressing	grilled pollack, dill dressing parsley potatoes, fair trade rice Asian fried rice with cashews corn tortilla, chili con carne, chili sin carne mixed peppers, tomatoes, onion slices iceberg lettuce, corn, chili and herbs dip guacamole, tomato salsa Salad buffet: tomatoes, white cabbage, cucumber, onion slices, carrots, mixed bell peppers, corn, hot peperonis, lollo bianco, green lettuce, radiccio, chive-mustard dressing	pork loin, hot peperoni sauce tagliatelle, bell peppers salad breaded chicken breast fillet, lemon, cream sauce Potato Buffet: twister fries, steakhouse fries, potato wedges, sweet potato fries, broccoli-potato casserole Vegan: hot chili dip tomato and cream cheese dip Vegan: garlic and herb dip ketchup Salad Bar: tomato, white cabbage, cucumber onion slices, carrots, mixed bell pepper corn, hot peperonis, lollo lianco curled lettuce, radicchio chive-mustard dressing	Greek vegetable skillet with rice shish kebab, onion sauce, steakhouse fries turkey breast with sweet-sour chinese vegetables gyros turkey, pork, soy or lamb gyros, flatbread, garlic sauce, peperoni, cucumber, iceberg lettuce, tomato slices white cabbage Salad buffet: tomato, white cabbage, cucumber, onion slices, carrots, mixed bell peppers, corn, hot peperonis, lollo bianco curled lettuce, radicchio chive-mustard dressing