6 citations · 7 across the 4 of their papers we have counts for
10 papers
A time and space optimal stable population protocol solving exact majority
David Doty, Mahsa Eftekhari, Leszek Gąsieniec +3
We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange info…
The Dynamic k-Mismatch Problem
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka +2
The text-to-pattern Hamming distances problem asks to compute the Hamming distances between a given pattern of length and all length- substrings of a given text of length $n…
Cardinality estimation using Gumbel distribution
Aleksander Łukasiewicz, Przemysław Uznański
Cardinality estimation is the task of approximating the number of distinct elements in a large dataset with possibly repeating elements. LogLog and HyperLogLog (c.f. Durand and Fla…
All-Pairs LCA in DAGs: Breaking through the barrier
Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz +2
Let be an -vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices and is a common ancestor of and such that no descend…
Improved Circular -Mismatch Sketches
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz +2
The shift distance between two strings and of the same length is defined as the minimum Hamming distance between and any rotation (cyclic s…
An Efficient Noisy Binary Search in Graphs via Median Approximation
Dariusz Dereniowski, Aleksander Łukasiewicz, Przemysław Uznański
Consider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a…
Approximating Text-to-Pattern Distance via Dimensionality Reduction
Przemysław Uznański
Text-to-pattern distance is a fundamental problem in string matching, where given a pattern of length and a text of length , over an integer alphabet, we are asked to comput…
A Framework for Searching in Graphs in the Presence of Errors
Dariusz Dereniowski, Stefan Tiegel, Przemysław Uznański +1
We consider the problem of searching for an unknown target vertex in a (possibly edge-weighted) graph. Each \emph{vertex-query} points to a vertex and the response either a…
Population Protocols Are Fast
Adrian Kosowski, Przemysław Uznański
A population protocol describes a set of state change rules for a population of indistinguishable finite-state agents (automata), undergoing random pairwise interactions. Withi…
All-Pairs 2-Reachability in Time
Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano +2
In the -reachability problem we are given a directed graph and we wish to determine if there are two (edge or vertex) disjoint paths from to , for a given pair of ver…