10 citations · 43 across the 22 of their papers we have counts for
7 papers · 1 filter
Hamming distance completeness and sparse matrix multiplication
Daniel Graf, Karim Labib, Przemysław Uznański
We show that a broad class of vector products (for binary integer functions ) are equivalent under one-to-polylog reductions to the computation of the Hamm…
Distributed Colour Reduction Revisited
Jukka Kohonen, Janne H. Korhonen, Christopher Purcell +2
We give a new, simple distributed algorithm for graph colouring in paths and cycles. Our algorithm is fast and self-contained, it does not need any globally consistent orientation,…
Energy Constrained Depth First Search
Shantanu Das, Dariusz Dereniowski, Przemysław Uznański
Depth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree…
Robust Detection in Leak-Prone Population Protocols
Dan Alistarh, Bartłomiej Dudek, Adrian Kosowski +2
In contrast to electronic computation, chemical computation is noisy and susceptible to a variety of sources of error, which has prevented the construction of robust complex system…
Optimal trade-offs for pattern matching with mismatches
Paweł Gawrychowski, Przemysław Uznański
Given a pattern of length and a text of length , the goal in -mismatch pattern matching is to compute, for every -substring of the text, the exact Hamming distance to…
Approximation Strategies for Generalized Binary Search in Weighted Trees
Dariusz Dereniowski, Adrian Kosowski, Przemyslaw Uznanski +1
We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node in a given tree . Upon querying a node…
LCL problems on grids
Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen +6
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cy…