10 citations · 43 across the 22 of their papers we have counts for
24 papers · 1 filter
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 …
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…
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…
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…
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…
Sublinear-Space Distance Labeling using Hubs
Paweł Gawrychowski, Adrian Kosowski, Przemysław Uznański
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…
On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols
Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski +3
In this work we focus on a natural class of population protocols whose dynamics are modelled by the discrete version of Lotka-Volterra equations. In such protocols, when an agent $…
Time and space optimality of rotor-router graph exploration
Artur Menc, Dominik Pająk, Przemysław Uznański
We consider the problem of exploration of an anonymous, port-labeled, undirected graph with nodes and edges and diameter , by a single mobile agent. Initially the agent…
Tight tradeoffs for approximating palindromes in streams
Paweł Gawrychowski, Przemysław Uznański
We consider computing the longest palindrome in a text of length in the streaming model, where the characters arrive one-by-one, and we do not have random access to the input.…
Rendezvous of Distance-aware Mobile Agents in Unknown Graphs
Shantanu Das, Dariusz Dereniowski, Adrian Kosowski +1
We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However t…
Improved Analysis of Deterministic Load-Balancing Schemes
Petra Berenbrink, Ralf Klasing, Adrian Kosowski +2
We consider the problem of deterministic load balancing of tokens in the discrete model. A set of processors is connected into a -regular undirected network. In every time s…
Order-preserving pattern matching with k mismatches
Pawel Gawrychowski, Przemyslaw Uznanski
We study a generalization of the recently introduced order-preserving pattern matching, where instead of looking for an exact copy of the pattern, we only require that the relative…