Przemyslaw Uznanski

Last Name

Uznanski

First Name

Przemyslaw

ORCID

0000-0002-8652-0490

Show all metadata

Search Results

Publications 1 - 10 of 10

A Framework for Searching in Graphs in the Presence of Errors
Dereniowski, Dariusz; Tiegel, Stefan; Uznanski, Przemyslaw; et al. (2019)
OpenAccess Series in Informatics (OASIcs) ~ 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
We consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide algorithms for the error-less case and for the independent noise model (where each query independently receives an erroneous answer with known probability p<1/2 and a correct one with probability 1-p). We study this problem both with adversarial errors and independent noise models. First, we show an algorithm that needs at most (log_2 n)/(1 - H(r)) queries in case of adversarial errors, where the adversary is bounded with its rate of errors by a known constant r<1/2. Our algorithm is in fact a simplification of previous work, and our refinement lies in invoking an amortization argument. We then show that our algorithm coupled with a Chernoff bound argument leads to a simpler algorithm for the independent noise model and has a query complexity that is both simpler and asymptotically better than the one of Emamjomeh-Zadeh et al. [STOC 2016]. Our approach has a wide range of applications. First, it improves and simplifies the Robust Interactive Learning framework proposed by Emamjomeh-Zadeh and Kempe [NIPS 2017]. Secondly, performing analogous analysis for edge-queries (where a query to an edge e returns its endpoint that is closer to the target) we actually recover (as a special case) a noisy binary search algorithm that is asymptotically optimal, matching the complexity of Feige et al. [SIAM J. Comput. 1994]. Thirdly, we improve and simplify upon an algorithm for searching of unbounded domains due to Aslam and Dhagat [STOC 1991].
Hamming distance completeness
Labib, Karim; Uznanski, Przemyslaw; Wolleb-Graf, Daniel (2019)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
We show, given a binary integer function diamond that is piecewise polynomial, that (+,diamond) vector products are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include the dominance and l_{2p+1} distances for constant p. Our results imply equivalence (up to polylog factors) between the complexity of computing All Pairs Hamming Distance, All Pairs l_{2p+1} Distance and Dominance Matrix Product, and equivalence between Hamming Distance Pattern Matching, l_{2p+1} Pattern Matching and Less-Than Pattern Matching. The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are likely to be optimal, given lack of progress in improving upper bounds for Hamming distance in the past 30 years. While reductions between selected pairs of products were presented in the past, our work is the first to generalize them to a general class of functions, showing that a wide class of "intermediate" complexity problems are in fact equivalent.
Randomized algorithms for finding a majority element
Gawrychowski, Pawel; Suomela, Jukka; Uznanski, Przemyslaw (2016)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Given n colored balls, we want to detect if more than n/2 of them have the same color, and if so find one ball with such majority color. We are only allowed to choose two balls and compare their colors, and the goal is to minimize the total number of such operations. A well-known exercise is to show how to find such a ball with only 2n comparisons while using only a logarithmic number of bits for bookkeeping. The resulting algorithm is called the Boyer-Moore majority vote algorithm. It is known that any deterministic method needs 3n/2-2 comparisons in the worst case, and this is tight. However, it is not clear what is the required number of comparisons if we allow randomization. We construct a randomized algorithm which always correctly finds a ball of the majority color (or detects that there is none) using, with high probability, only 7n/6+o(n) comparisons. We also prove that the expected number of comparisons used by any such randomized method is at least 1.019n.
Lp Pattern Matching in a Stream
Starikovskaya, Tatiana; Svagerka, Michal; Uznanski, Przemyslaw (2020)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
We consider the problem of computing distance between a pattern of length n and all n-length subwords of a text in the streaming model. In the streaming setting, only the Hamming distance (L0) has been studied. It is known that computing the exact Hamming distance between a pattern and a streaming text requires Ω(n) space (folklore). Therefore, to develop sublinear-space solutions, one must relax their requirements. One possibility to do so is to compute only the distances bounded by a threshold k, see [SODA'19, Clifford, Kociumaka, Porat] and references therein. The motivation for this variant of this problem is that we are interested in subwords of the text that are similar to the pattern, i.e. in subwords such that the distance between them and the pattern is relatively small. On the other hand, the main application of the streaming setting is processing large-scale data, such as biological data. Recent advances in hardware technology allow generating such data at a very high speed, but unfortunately, the produced data may contain about 10% of noise [Biol. Direct.'07, Klebanov and Yakovlev]. To analyse such data, it is not sufficient to consider small distances only. A possible workaround for this issue is the (1 ± ε)-approximation. This line of research was initiated in [ICALP'16, Clifford and Starikovskaya] who gave a (1 ± ε)-approximation algorithm with space Oe(ε−5 √n). In this work, we show a suite of new streaming algorithms for computing the Hamming, L1, L2 and general Lp (0 < p < 2) distances between the pattern and the text. Our results significantly extend over the previous result in this setting. In particular, for the Hamming distance and for the Lp distance when 0 < p ≤ 1 we show a streaming algorithm that uses Oe(ε−2 √n) space for polynomial-size alphabets.
Brief announcement: Population protocols are fast
Kosowski, Adrian; Uznanski, Przemyslaw (2018)
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18
Brief announcement: Energy constrained depth first search
Das, Shantanu; Dereniowski, Dariusz; Uznanski, Przemyslaw (2018)
Leibniz International Proceedings in Informatics (LIPIcs)
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, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer B (e.g. due to limited energy resources of the searcher). The objective is to cover all the edges of a tree T using the minimum number of routes, each starting and ending at the root and each being of length at most B. To this end, we analyze the following natural greedy tree traversal process that is based on decomposing a depth first search traversal into a sequence of limited length routes. Given any arbitrary depth first search traversal R of the tree T, we cover R with routes R_1,...,R_l, each of length at most B such that: R_i starts at the root, reaches directly the farthest point of R visited by R_{i-1}, then R_i continues along the path R as far as possible, and finally R_i returns to the root. We call the above algorithm piecemeal-DFS and we prove that it achieves the asymptotically minimal number of routes l, regardless of the choice of R. Our analysis also shows that the total length of the traversal (and thus the traversal time) of piecemeal-DFS is asymptotically minimum over all energy-constrained exploration strategies. The fact that R can be chosen arbitrarily means that the exploration strategy can be constructed in an online fashion when the input tree T is not known in advance. Each route R_i can be constructed without any knowledge of the yet unvisited part of T. Surprisingly, our results show that depth first search is efficient for energy constrained exploration of trees, even though it is known that the same does not hold for energy constrained exploration of arbitrary graphs.
Improved Analysis of Deterministic Load-Balancing Schemes
Berenbrink, Petra; Klasing, Ralf; Kosowski, Adrian; et al. (2019)
ACM Transactions on Algorithms
Approximating approximate pattern matching
Studený, Jan; Uznanski, Przemyslaw (2019)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Given a text T of length n and a pattern P of length m, the approximate pattern matching problem asks for computation of a particular distance function between P and every m-substring of T. We consider a (1 +/- epsilon) multiplicative approximation variant of this problem, for l_p distance function. In this paper, we describe two (1+epsilon)-approximate algorithms with a runtime of O~(n/epsilon) for all (constant) non-negative values of p. For constant p >= 1 we show a deterministic (1+epsilon)-approximation algorithm. Previously, such run time was known only for the case of l_1 distance, by Gawrychowski and Uznanski [ICALP 2018] and only with a randomized algorithm. For constant 0 <= p <= 1 we show a randomized algorithm for the l_p, thereby providing a smooth tradeoff between algorithms of Kopelowitz and Porat [FOCS 2015, SOSA 2018] for Hamming distance (case of p=0) and of Gawrychowski and Uznanski for l_1 distance.
Towards unified approximate pattern matching for hamming and L1 Distance
Gawrychowski, Paweł; Uznanski, Przemyslaw (2018)
Leibniz International Proceedings in Informatics (LIPIcs)
Computing the distance between a given pattern of length n and a text of length m is defined as calculating, for every m-substring of the text, the distance between the pattern and the sub- string. This naturally generalizes the standard notion of exact pattern matching to incorporate dissimilarity score. For both Hamming and L1 distance only relatively slow O(n√m) solutions are known for this generalization. This can be overcome by relaxing the question. For Hamming distance, the usual relaxation is to consider the k-bounded variant, where distances exceeding k are reported as ∞, while for L1 distance asking for a(1±ε)-approximation seems more natural. For k -bounded Hamming distance, Amir et al. [J. Algorithms 2004] showed an O(n√k) time algorithm, and Clifford et al. [SODA 2016] designed an O((m+k2) ·n/m) time solution. We provide a smooth time trade-off between these bounds by exhibiting an O((m+k√m) ·n/m) time algorithm. We complement the trade-off with a matching conditional lower bound, show-ing that a significantly faster combinatorial algorithm is not possible, unless the combinatorial matrix multiplication conjecture fails. We also exhibit a series of reductions that together allow us to achieve essentially the same complexity for k-bounded L1 distance. Finally, for (1±ε)- approximate L1 distance, the running time of the best previously known algorithm of Lipsky and Porat [Algorithmica 2011] was O(ε−2n). We improve this to O(ε−1n), thus essentially matching the complexity of the best known algorithm for (1±ε) -approximate Hamming distance.
Brief announcement: Hamming distance completeness and sparse matrix multiplication
Wolleb, Daniel Stefan; Labib, Karim; Uznanski, Przemyslaw (2018)
Leibniz International Proceedings in Informatics (LIPIcs)
We show that a broad class of (+, diamond) vector products (for binary integer functions diamond) are equivalent under one-to-polylog reductions to the computation of the Hamming distance. Examples include: the dominance product, the threshold product and l_{2p+1} distances for constant p. Our results imply equivalence (up to poly log n factors) between complexity of computation of All Pairs: Hamming Distances, l_{2p+1} Distances, Dominance Products and Threshold Products. As a consequence, Yuster's (SODA'09) algorithm improves not only Matousek's (IPL'91), but also the results of Indyk, Lewenstein, Lipsky and Porat (ICALP'04) and Min, Kao and Zhu (COCOON'09). Furthermore, our reductions apply to the pattern matching setting, showing equivalence (up to poly log n factors) between pattern matching under Hamming Distance, l_{2p+1} Distance, Dominance Product and Threshold Product, with current best upperbounds due to results of Abrahamson (SICOMP'87), Amir and Farach (Ann. Math. Artif. Intell.'91), Atallah and Duket (IPL'11), Clifford, Clifford and Iliopoulous (CPM'05) and Amir, Lipsky, Porat and Umanski (CPM'05). The resulting algorithms for l_{2p+1} Pattern Matching and All Pairs l_{2p+1}, for 2p+1 = 3,5,7,... are new. Additionally, we show that the complexity of AllPairsHammingDistances (and thus of other aforementioned AllPairs- problems) is within poly log n from the time it takes to multiply matrices n x (n * d) and (n * d) x n, each with (n * d) non-zero entries. This means that the current upperbounds by Yuster (SODA'09) cannot be improved without improving the sparse matrix multiplication algorithm by Yuster and Zwick (ACM TALG'05) and vice versa.

Publications 1 - 10 of 10

Przemyslaw Uznanski

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results