“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 03.03.2016 as a part of our Foundation 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.
On 21.01.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
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 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
On 18.06.2015 as a part of our 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:
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.