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

Participants

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

24.03.2014