Zobrazeno 1 - 10
of 63
pro vyhledávání: '"YOGEV, EYLON"'
Distributional collision resistance is a relaxation of collision resistance that only requires that it is hard to sample a collision $(x,y)$ where $x$ is uniformly random and $y$ is uniformly random conditioned on colliding with $x$. The notion lies
Externí odkaz:
http://arxiv.org/abs/2105.00710
Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the
Externí odkaz:
http://arxiv.org/abs/2101.09054
Publikováno v:
J. ACM 69, 2, Article 17 (April 2022)
We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorith
Externí odkaz:
http://arxiv.org/abs/2003.14265
Autor:
Ben-Eliezer, Omri, Yogev, Eylon
Random sampling is a fundamental primitive in modern algorithms, statistics, and machine learning, used as a generic method to obtain a small yet "representative" subset of the data. In this work, we investigate the robustness of sampling against ada
Externí odkaz:
http://arxiv.org/abs/1906.11327
We study parallel algorithms for the classical balls-into-bins problem, in which $m$ balls acting in parallel as separate agents are placed into $n$ bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages onc
Externí odkaz:
http://arxiv.org/abs/1904.07532
We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of $n$ nodes and a graph $G$ that defines their communication pattern. The prover is a single entity that communicates with all nodes by sh
Externí odkaz:
http://arxiv.org/abs/1812.10917
Autor:
Parter, Merav, Yogev, Eylon
A cycle cover of a bridgeless graph $G$ is a collection of simple cycles in $G$ such that each edge $e$ appears on at least one cycle. The common objective in cycle cover computation is to minimize the total lengths of all cycles. Motivated by applic
Externí odkaz:
http://arxiv.org/abs/1812.04492
Autor:
Parter, Merav, Yogev, Eylon
Graph spanners are sparse subgraphs that faithfully preserve the distances in the original graph up to small stretch. Spanner have been studied extensively as they have a wide range of applications ranging from distance oracles, labeling schemes and
Externí odkaz:
http://arxiv.org/abs/1805.05404
Autor:
Parter, Merav, Yogev, Eylon
In the area of distributed graph algorithms a number of network's entities with local views solve some computational task by exchanging messages with their neighbors. Quite unfortunately, an inherent property of most existing distributed algorithms i
Externí odkaz:
http://arxiv.org/abs/1712.01139
Publikováno v:
Journal of the ACM; Aug2023, Vol. 70 Issue 4, p1-62, 62p
