#
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

*Abstract:*

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

*Abstract:*

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