6 papers
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…
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…