# Miniworkshop on 28.05.2015

On 28.05.2015 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will host Giuseppe F. Italiano from  University of Rome “Tor Vergata”. He will give a talk on his recent result on “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching”. The abstract is given below.

We plan to have a group discussion and joint hamburger lunch after his talk.

Abstract:

We present the first deterministic data structures for maintaining
approximate  minimum vertex cover and maximum matching in a fully
dynamic graph in $o(\sqrt{m}\,)$ time per update. In particular, for
minimum vertex cover we provide deterministic data structures for
maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized
time per update. For maximum matching, we  show how to  maintain a
$(3+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em amortized} time
per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em
worst-case} time per update. Our data structure for fully dynamic
minimum vertex cover is essentially near-optimal and settles an open
problem by Onak and Rubinfeld~\cite{OnakR10}.

Joint work with Sayan Bhattacharya and Monika Henzinger.

# Topics of the next few lectures

The lectures were based on the following papers:
8. Lecture by Erik Demaine on Van Emde Boas trees: http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf
9. Lecture by Erik Demaine on Ordered List Maintenance: http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L14/lecture14.pdf
11. Paper on pattern matching in dynamic texts: http://www.cs.au.dk/~gerth/papers/diku-98-27.pdf

# Miniworkshop on 14.05.2015

On 14.05.2015 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will host Artur Czumaj from University of Warwick. He will give a talk on his recent result on “Random permutations using switching networks”. The abstract is given below.

We plan to have a group discussion and joint hamburger lunch after his talk.

Abstract:

We consider the problem of designing a simple, oblivious scheme to generate (almost) random permutations. We use the concept of switching networks and show that almost every switching network of logarithmic depth can be used to almost randomly permute any set of (1-epsilon)n elements with any epsilon>0 (that is, gives an almost (1-epsilon)n-wise independent permutation). Furthermore, we show that the result still holds for every switching network of logarithmic depth that has some special expansion properties, leading to an explicit construction of such networks. Our result can be also extended to an explicit construction of a switching network of depth O(log^2n) and with O(n log n) switches that almost randomly permutes any set of n elements. We also briefly discuss basic applications of these results in cryptography.

Our results are obtained using a non-trivial coupling approach to study mixing times of Markov chains which allows us to reduce the problem to some random walk-like problem on expanders.