Zobrazeno 1 - 10
of 90
pro vyhledávání: '"Uznański, Przemysław"'
Autor:
Uznanski, Przemyslaw
La popularité croissante des applications Internet très gourmandes en bande passante (P2P, streaming,...) nous pousse à considérer le problème suivant :Comment construire des systèmes de communications collectives efficaces sur une plateforme
Externí odkaz:
http://www.theses.fr/2013BOR14872/document
Autor:
Bartoszkiewicz, Michal, Chorowski, Jan, Kosowski, Adrian, Kowalski, Jakub, Kulik, Sergey, Lewandowski, Mateusz, Nowicki, Krzysztof, Piechowiak, Kamil, Ruas, Olivier, Stamirowska, Zuzanna, Uznanski, Przemyslaw
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 motivation of resolving challenges faced when analyzing and processing data fro
Externí odkaz:
http://arxiv.org/abs/2307.13116
This work considers the problem of the noisy binary search in a sorted array. The noise is modeled by a parameter $p$ that dictates that a comparison can be incorrect with probability $p$, independently of other queries. We state two types of upper b
Externí odkaz:
http://arxiv.org/abs/2107.05753
Autor:
Doty, David, Eftekhari, Mahsa, Gąsieniec, Leszek, Severson, Eric, Stachowiak, Grzegorz, Uznański, Przemysław
Publikováno v:
FOCS 2021: Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, Feb 2022
We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their sched
Externí odkaz:
http://arxiv.org/abs/2106.10201
Autor:
Clifford, Raphaël, Gawrychowski, Paweł, Kociumaka, Tomasz, Martin, Daniel P., Uznański, Przemysław
The text-to-pattern Hamming distances problem asks to compute the Hamming distances between a given pattern of length $m$ and all length-$m$ substrings of a given text of length $n\ge m$. We focus on the $k$-mismatch version of the problem, where a d
Externí odkaz:
http://arxiv.org/abs/2105.06166
In this paper we study population protocols governed by the {\em random scheduler}, which uniformly at random selects pairwise interactions between $n$ agents. The main result of this paper is the first time and space optimal {\em exact majority popu
Externí odkaz:
http://arxiv.org/abs/2011.07392
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 Flajolet [ESA 2003], Flajolet et al. [Discrete Math Theor. 2007]) are sma
Externí odkaz:
http://arxiv.org/abs/2008.07590
Autor:
Grandoni, Fabrizio, Italiano, Giuseppe F., Łukasiewicz, Aleksander, Parotsidis, Nikos, Uznański, Przemysław
Let $G=(V,E)$ be an $n$-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices $u$ and $v$ is a common ancestor $w$ of $u$ and $v$ such that no descendant of $w$ has the same property. In this paper, we consider the probl
Externí odkaz:
http://arxiv.org/abs/2007.08914
The shift distance $\mathsf{sh}(S_1,S_2)$ between two strings $S_1$ and $S_2$ of the same length is defined as the minimum Hamming distance between $S_1$ and any rotation (cyclic shift) of $S_2$. We study the problem of sketching the shift distance,
Externí odkaz:
http://arxiv.org/abs/2006.13673
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 strategy, that identifies an initially unknown target vertex in a gra
Externí odkaz:
http://arxiv.org/abs/2005.00144