Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, June 28th, 2010

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25,
12489 Berlin
room 4.112

Lecture - 14:15

Dieter van Melkebeek - Madison WI

Derandomizing Polynomial Identity Testing

Derandomization constitutes a central theme in the theory of computing. It involves the design of efficient deterministic simulations of randomized processes.

In this talk we will survey some of the approaches and bottlenecks towards derandomizing polynomial identity testing, the fundamental problem of deciding whether a given polynomial identity holds. The problem has a natural and efficient randomized algorithm, but efficient deterministic algorithms for the general case have remained elusive.

We will discuss the connection with circuit lower bounds, present the key ingredients in recent progress for special cases, and illustrate them in a simple setting.

Colloquium - 16:00

Siamak Tazari - HU Berlin

Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs

We improve the running time of the general algorithmic technique known as Baker's approach (1994) on H-minor-free graphs from O(n^{f(|H|)}) to O(f(|H|) n^{O(1)}). The numerous applications include e.g. a 2-approximation for coloring and PTASes for various problems such as dominating set and max-cut, where we obtain similar improvements.

On classes of odd-minor-free graphs, which have gained significant attention in recent time, we obtain a similar acceleration for a variant of the structural decomposition theorem proved by Demaine et al. (2010). We use these algorithms to derive faster 2-approximations; furthermore, we present the first PTASes and subexponential FPT-algorithms for independent set and vertex cover on these graph classes using a novel dynamic programming technique.

We also introduce a technique to derive (nearly) subexponential parameterized algorithms on H-minor-free graphs. Our technique applies, in particular, to problems such as Steiner tree, (directed) subgraph with a property, (directed) longest path, and (connected/independent) dominating set, on some or all proper minor-closed graph classes. We obtain as a corollary that all problems with a minor-monotone subexponential kernel and amenable to our technique can be solved in subexponential FPT-time on H-minor free graphs. This results in a general methodology for subexponential parameterized algorithms outside the framework of bidimensionality.

Letzte Aktualisierung: 16.06.2010