10 citations · 43 across the 22 of their papers we have counts for
32 papers
Rectangular matrix multiplication from polynomial products
Przemyslaw Uznanski
In this note, we extend the matrix-multiplication analysis by OpenAI to rectangular products and prove for , and …
Pathway: a fast and flexible unified stream data processing framework for analytical and Machine Learning applications
Michal Bartoszkiewicz, Jan Chorowski, Adrian Kosowski +8
We present Pathway, a new unified data processing framework that can run workloads on both bounded and unbounded data streams. The framework was created with the original motivatio…
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…
Robust Comparison in Population Protocols
Dan Alistarh, Martin Töpfer, Przemysław Uznański
There has recently been a surge of interest in the computational and complexity properties of the population model, which assumes anonymous, computationally-bounded nodes, inte…
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…
Almost logarithmic-time space optimal leader election in population protocols
Leszek Gąsieniec, Grzegorz Stachowiak, Przemysław Uznański
The model of population protocols refers to a large collection of simple indistinguishable entities, frequently called {\em agents}. The agents communicate and perform computation…
Faster Approximate(d) Text-to-Pattern L1 Distance
Przemysław Uznański
The problem of finding \emph{distance} between \emph{pattern} of length and \emph{text} of length is a typical way of generalizing pattern matching to incorporate dissimila…
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…
Ergodic Effects in Token Circulation
Adrian Kosowski, Przemysław Uznański
We consider a dynamical process in a network which distributes all particles (tokens) located at a node among its neighbors, in a round-robin manner. We show that in the recurrent…
A note on distance labeling in planar graphs
Paweł Gawrychowski, Przemysław Uznański
A distance labeling scheme is an assignments of labels, that is binary strings, to all nodes of a graph, so that the distance between any two nodes can be computed from their label…
Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams
Paweł Gawrychowski, Oleg Merkurev, Arseny M. Shur +1
We consider computing a longest palindrome in the streaming model, where the symbols arrive one-by-one and we do not have random access to the input. While computing the answer exa…
Randomized algorithms for finding a majority element
Paweł Gawrychowski, Jukka Suomela, Przemysław Uznański
Given colored balls, we want to detect if more than of them have the same color, and if so find one ball with such majority color. We are only allowed to c…
Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
Matúš Mihalák, Przemysław Uznański, Pencho Yordanov
We study the problem of enumerating all rooted directed spanning trees (arborescences) of a directed graph (digraph) of vertices. An arborescence consisting of ed…
All Permutations Supersequence is coNP-complete
Przemysław Uznański
We prove that deciding whether a given input word contains as subsequence every possible permutation of integers is coNP-complete. The coNP-completeness holds ev…