Open Day of Doctoral Studies in Computer Science

“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 starts today at 11AM!

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!

Miniworkshop on 03.03.2016

On 03.03.2016 as a part of our logo FNPFoundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Krzysztof Sormat. He will give a talk on his recent result on “PTAS for Minimax Approval Voting”. The abstract is given below.

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

Abstract: J. Byrka, K. Sornat. PTAS for Minimax Approval Voting. WINE 2014.

http://arxiv.org/abs/1407.7216

We consider Approval Voting systems where each voter decides on a subset to candidates he/she approves. We focus on the optimization problem of finding the committee of fixed size k minimizing the maximal Hamming distance from a vote. In this paper we give a PTAS for this problem and hence resolve the open question raised by Carragianis et al. [AAAI’10]. The result is obtained by adapting the techniques developed by Li et al. [JACM’02] originally used for the less constrained Closest String problem. The technique relies on extracting information and structural properties of constant size subsets of votes.

Miniworkshop on 21.01.2016

On 21.01logo FNP.2016 as a part of our Foundation for Polish Science Algorithmic Miniworkshop series we will have a seminar by Tomasz Kociumaka. He will give a talk on his recent result on “Optimal Dynamic Strings”. The abstract is given below.

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

Abstract:

We study the fundamental problem of maintaining a dynamic collection
of strings under the following operations: concatenate two strings,
split a string into two at a given position, determine the
lexicographical order (smaller, equal, greater) between two strings,
calculate the longest common prefix of two strings. We present a data
structure for this problem, in which updates require only O(log n)
worst-case time with high probability, with n being the total length
of all strings in the collection, and queries take constant worst-case
time. On the lower bound side, we prove that even if the only possible
query is checking equality of two strings, either updates or queries
must take amortized Ω(log n) time; hence our implementation is
optimal. Our data structure can be used as a basic building block to
solve other string problems, such as pattern matching in dynamic
string collections, pattern matching in a history is an edited text,
and processing grammar-compressed strings.

Joint work with Paweł Gawrychowski, Jakub Łącki, Adam Karczmarz, and Piotr Sankowski

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 12.11.2015

Onlogo FNP 12.11.2015 as a part of our Foundation for Polish Science  Algorithmic Miniworkshop series we will host Ariel Gabizon from Technion. He will give a talk on his recent result on “Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints”. The abstract is given below.

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

Abstract:

We consider generalized versions of well-studied problems in parameterized complexity and exact exponential time algorithms. The generalizations are obtained by introducing a relaxation parameter, which relaxes the constraints on feasible solutions. For example, one can generalize Hamiltonian path to the problem of finding a spanning tree where all degrees are at most some integer d. Or one can generalize k-Path to the task of finding a walk of length k where any vertex is visited at most r times. This problem was first considered by Abasi et. al who showed a randomized algorithm where the running time improves with the parameter r. We derandomize their algorithm. We also obtain an algorithm for Bounded-Degree Spanning Tree, where the running time improves with the degree bound d, improving an algorithm of Fomin et al. with running time 2^{n+o(n)} for any d.On the way to obtain our results we generalize the notion of representative sets to multisets, and give an efficient algorithm to compute such representative sets. Both the generalization of representative sets to multisets and the algorithm to compute them may be of independent interest.Joint work with Daniel Lokshtanov and Michał Pilipcuzk

 

Miniworkshop on 18.06.2015

On 18.06.2015 as a part of our logo FNP Foundation for Polish Science Algorithmic Miniworkshop series we will host Evangelos Kranakis from Carleton University. He will give a talk on his recent result on “Robot Evacuation”. The abstract is given below.

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

Abstract:

Consider k mobile robots inside a circular disk of unit radius. The robots are required to evacuate the disk through an unknown exit point situated on its boundary. We assume all robots having the same (unit) maximal speed and  starting at the centre of the disk. The robots may communicate in order to inform themselves about the presence (and its position) or the absence of an exit. The goal is for all the robots to evacuate
through the exit in minimum time.
We consider two  models of communication between the robots: in non-wireless (or local) communication model robots exchange information only when simultaneously located at the same point, and wireless communication in which robots can communicate one another at any time.
We study the following question what is the optimal evacuation time for k robots?

 

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.

 

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

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.