10 citations · 10 across the 4 of their papers we have counts for
12 papers
Time and Space Optimal Exact Majority Population Protocols
Leszek Gąsieniec, Grzegorz Stachowiak, Przemysław Uznański
In this paper we study population protocols governed by the {\em random scheduler}, which uniformly at random selects pairwise interactions between agents. The main result of t…
Pattern Matching in a Stream
Tatiana Starikovskaya, Michal Svagerka, Przemysław Uznański
We consider the problem of computing distance between a pattern of length and all -length subwords of a text in the streaming model. In the streaming setting, only the Hammi…
RLE edit distance in near optimal time
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka +2
We show that the edit distance between two run-length encoded strings of compressed lengths and respectively, can be computed in time. This improv…
Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
Adrian Kosowski, Przemysław Uznański, Laurent Viennot
A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded sole…
Approximating Approximate Pattern Matching
Jan Studený, Przemysław Uznański
Given a text of length and a pattern of length , the approximate pattern matching problem asks for computation of a particular \emph{distance} function between a…
Faster Algorithms for All-Pairs Bounded Min-Cuts
Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano +5
The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum - cut (or just its value) for all pairs of vertices . We study this problem in directed…