Winter School 2014
Finse
Main content
The 12th Annual Winter School in Algorithms, Graph Theory and Combinatorics will take place March 19-21, 2014, in Finse at Hotel 1222 Finse.
Program
Final Program
Wednesday March 19:
07:58 : Departure from Bergen by train (bring with you packed lunch and afternoon snack)
Skiing / leisure
17:00 - 18:00 : Introduction to Circuit Complexity
18:15 - 19:15 : Presentations by master students
19:30 - 20:30 : Rump session
21:00 : Dinner
Thursday March 20:
08:00 - 08:45 : Breakfast (and pack your lunch and afternoon snack)
09:00 - 10:15 : Lecture on Circuit Complexity
10:45 - 12:00 : New developments on Circuit Complexity
Skiing / leisure
17:00 - 18:00 : Introduction to LP Branching
18:15 - 19:15 : Presentations by master students
19:30 - 20:30 : Rump session
21:00 : Dinner
Friday March 21:
08:00 - 08:45 : Breakfast (and pack your lunch)
09:00 - 10:15 : New developments on LP Branching
10:30 - 11:10 : Invited talk
11:20 - 12:00 : Guest talk
Skiing / leisure
16:31 : Train to Bergen
(We take care of scheduled meals, accommodation, and train tickets for all invited participants.)
Participants
Confirmed participants
Manu Basavaraju
Jo Inge Bitubekk
Ivan Bliznets
Pål Drange
Markus Dregi
Erlend Fasmer
Jiri Fiala
Fedor Fomin
Petr Golovach
Johan Halseth
Håvard Haug
Pinar Heggernes
Marit Hellestø
Pim van 't Hof
Bart Jansen
Martin Koutecky
Alexander Kulikov
Mithilesh Kumar
Simen Lilleeng
Daniel Lokshtanov
Fredrik Manne
Ivan Myhailin
Magnar Myrtveit
Erik Måland
Md Naim
Yevgheni Petkevich
Marcin Pilipczuk
Michał Pilipczuk
M S Ramanujan
Felix Reidl
Johan Rusvik
Reza Saei
Sadia Sharmin
Somnath Sikdar
Sigve Sæther
Jan Arne Telle
Marek Tesar
Martin Vatshelle
Fernando Villaamil
Yngve Villanger
(Participation is normally by invitation only.)
Useful information
Scientific information
It is a good idea to gather some background on the main topics, LP Branching and Circuit Complexity, before coming to the school.
LP Branching: We will be working with LP (Linear Programming) relaxations of some problems. If you have no or little experience with LP programs, you may find it useful to look into some standard approximation algorithms textbook before the school. We recommend V. Vazirani's book "Approximation Algorithms"; please start with Chapters 12-14. We will particularly need the notion of half-integrality: Chapter 14.3 (vertex cover) and Chapter 19 (multiway cut).
Circut Complexity: The goal of the lectures is to highlight the role of efficient algorithms in circuit lower bounds, motivated by Ryan Williams' recent proof (STOC'10, CCC'11) that NEXP does not have polynomial-size ACC circuits: His result relies crucially on an algorithm that beats brute force for testing the satisfiability of an ACC circuit. To appreciate the result we will introduce the relevant classes of circuits and complexity-theoretic theorems, and describe some of the history of circuit lower bounds. If it has been a while since you looked at formal complexity theory, it might be a good idea to refresh your memory regarding (non-deterministic) Turing machines, complexity classes such as NP and NEXP, formal decision problems and circuits. The book Computational Complexity: A Modern Approach by Arora and Barak is a good resource for this; a draft is freely available online. The relevant background can be found in Chapters 1, 2, 3 and 6. To get a feel for the circuit lower bounds we will be discussing you could browse through Chapter 14. If you are curious why Williams' result is such a breakthrough, read Chapter 23. A "casual tour" of Williams' result is given by his informal article in SIGACT News but you do not have to read this to understand the lectures.
Practical information
Erik, Felix, Fernando, Fredrik, Jan Arne, Mithilesh, and Somnath are taking care of their own train tickets. For all of us others, below is our train information.
When you arrive at the station, you can directly go and take one of the seats in our booking:
Booking reference: 147438574 (Universitetet i Bergen)
BERGEN-FINSE Avreise 19/03 kl 07:58 - 10:16
Vogn 7
Seats 33--52, 55, 56, 58, 61--70.
FINSE-BERGEN Avreise 21/03 kl 16:31 - 19:00
Vogn 6
Seats 29--31, 37--66.
Photos
Photos from the winter school
If you have taken photos during the winter school, please send us a link to where they are stored, and we can place the link here.
