L3

Parity games are simple two-player, infinite-move games particularly useful in Computer Science for modelling non-terminating reactive systems and recursive processes.  A longstanding open problem related to these games is whether the winner of a parity game can be decided in polynomial time.  One of the most promising algorithms to date is a strategy improvement algorithm of Voege and Jurdzinski, however no good bounds are known on its running time.

In this talk I will discuss how the problem of finding a winner in a parity game can be reduced to the problem of locally finding a global sink on an acyclic unique sink oriented hypercube.  As a consequence, we can improve (albeit only marginally) the bounds of the strategy improvement algorithm.

This talk is similar to one I presented at the InfoSys seminar in the Computing Laboratory in October.

Regions of a link diagram can be colored in black and white in a checkerboard manner. Putting a vertex in each black region and connecting two vertices by an edge if the corresponding regions share a crossing yields a planar graph. In 1987 Thistlethwaite proved that the Jones polynomial of the link can be obtained by a specialization of the Tutte polynomial of this planar graph. The goal of my talk will be an explanation of a generalization of Thistlethwaite's theorem to virtual links. In this case graphs will be embedded into a (higher genus, possibly non-oriented) surface. For such graphs we used a generalization of the Tutte polynomial called the Bollobas-Riordan polynomial. For graphs on
surfaces the natural duality can be generalized to a duality with respect to a subset of edges. The generalized dual graph might be embedded into a different surface. I will explain a relation between the Bollobas-Riordan polynomials of dual graphs. This relation unifies various Thistlethwaite type theorems.

In the first part of the talk we will introduce the notion of property testing and briefly discuss some results in testing graph properties in the framework of property testing.

Then, we will discuss a recent result about testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion:   \newline an $a$-expander is a graph $G = (V,E)$ in which every subset $U$ of $V$ of at most $|V|/2$ vertices has a neighborhood of size at least $a|U|$. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately $O(n^{1/2})$.

We design a property testing algorithm that accepts every $a$-expander with probability at least 2/3 and rejects every graph that is $\epsilon$-far from an $a^*$-expander with probability at least 2/3, where $a^* = O(a^2/(d^2 log(n/\epsilon)))$, $d$ is the maximum degree of the graphs, and a graph is called $\epsilon$-far from an $a^*$-expander if one has to modify (add or delete) at least $\epsilon d n$ of its edges to obtain an $a^*$-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is $O(d^2 n^{1/2} log(n/\epsilon)/(a^2 \epsilon^3))$.

This is a joint work with Christian Sohler.

I will prove that certain pairs of ordered structures are dependent. There are basically two cases depending on whether the smaller structure is dense or discrete. I will discuss the proofs of two quite general theorems which construe the dividing line between these cases. Among examples are dense pairs of o-minimal structures in the first case, and tame pairs of o-minimal structures in the latter. This is joint work with P. Hieronymi.