Miniworkshop on 10.12.2015

logo FNPOn 10.12.2015 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Paweł Gawrychowski. He will give a talk on his recent result on “Approximating LZ77 via Small-Space Multiple-Pattern Matching”. The abstract is given below.

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

Abstract:

We generalize the well-known Karp-Rabin string matching to handle
multiple patterns in O(nlogn+m) time and O(s) space, where n is the
length of the text and m is the total length of the s patterns,
returning correct answers with high probability. As a prime
application of our algorithm, we show how to approximate the LZ77
parse of a string of length n. If the optimal parse consists of z
phrases, using only O(z) working space we can return a parse
consisting of at most (1+ε)z phrases in O(1/ε n logn) time, for any
ε∈(0,1].

Joint work with Johannes Fischer, Travis Gagie, and Tomasz Kociumaka.

Miniworkshop on 28.05.2015

On 28.05.2015 as a part logo FNPof 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.

 

Miniworkshop on 14.05.2015

Ologo FNPn 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.

The Talk on Online Bipartite Matching in Offline Time

The talk on The Talk on Online Bipartite Matching in Offline Time.