“Open Day of Doctoral Studies in Computer Science” will happen this Saturday. Here is the link to this event: https://lnkd.in/e9vdrnj.

“Open Day of Doctoral Studies in Computer Science” will happen this Saturday. Here is the link to this event: https://lnkd.in/e9vdrnj.

State of Polish AI 2021 starts today at 11 AM! Registration link for Zoom event 👉 https://lnkd.in/e8wX3PD.

There will be certainly some unexpected discoveries presented!

On 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.

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.

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.

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

The last lecture on network games.

Termin ostatniej podwójnej serii zadań to 20.06.2013: piąta i szósta seria zadań.

Czwarta seria zadan jest do oddania przed wykładem w dniu 05.06.2013.

Trzecia seria zadan jest do oddania w dniu 22 maja np. poprzez zostawienie w mojej przegrodce w sekretariacie.