Monday, June 28th, 2010
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25,
12489 Berlin
room 4.112
Lecture - 14:15
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
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.