Author name cluster

Ran Gelles

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

I&C Journal 2022 Journal Article

Noisy beeping networks

Yagel Ashkenazi
Ran Gelles
Amir Leshem

Beeping networks consist of exceedingly simple computational devices whose communication is based on beeps and silence. In this work, we introduce noisy beeping networks, where the observed communication is noisy with some fixed probability of error. We show how to transform any algorithm over a noiseless beeping network into a noise-resilient version while incurring a multiplicative overhead of essentially O ( log ⁡ n ) in its round complexity, with high probability. Our coding is optimal for some (short) tasks, such as the node-coloring of cliques. Interestingly, in the case of coloring, our technique achieves the same complexity as the standard beeping model while being noise resilient. We further show how to simulate a large family of algorithms designed for distributed networks in the CONGEST(B) model over a noisy beeping network, with a multiplicative overhead of O ( B ⋅ Δ ⋅ min ⁡ ( n, Δ 2 ) ) in the round complexity, where Δ is the maximum degree of the network.

Details DOI

STOC Conference 2016 Conference Paper

Constant-rate coding for multiparty interactive communication is impossible

Mark Braverman
Klim Efremenko
Ran Gelles
Bernhard Haeupler

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability ε. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise. Our main result is a lower bound on the communication of any noise-resilient protocol over a synchronous star network with n-parties (where all parties communicate in every round). Specifically, we show a task that can be solved by communicating T bits over the noise-free network, but for which any protocol with success probability of 1-o(1) must communicate at least Ω(T log n / log log n) bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a log log n factor. We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of (synchronous) star networks is Θ(log log n / log n). Our bounds prove that, despite several previous coding schemes with rate Ω(1) for certain topologies, no coding scheme with constant rate Ω(1) exists for arbitrary n-party noisy networks.

Details

SODA Conference 2016 Conference Paper

Towards Optimal Deterministic Coding for Interactive Communication

Ran Gelles
Bernhard Haeupler
Gillat Kol
Noga Ron-Zewi
Avi Wigderson

We study efficient, deterministic interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length. For channels that flip bits independently with probability ∊ < 1/2, our coding scheme achieves a communication rate of and a failure probability of exp(− n /log n ) in length n protocols. Prior to our work, all nontrivial deterministic schemes (either efficient or not) had a rate bounded away from 1. Furthermore, the best failure probability achievable by an efficient deterministic coding scheme with constant rate was only quasi-polynomial, i. e. , of the form exp(− log O (1) n ) (Braverman, ITCS 2012). For channels in which an adversary controls the noise pattern our coding scheme can tolerate Ω(1/log n ) fraction of errors with rate approaching 1. Once more, all previously known nontrivial deterministic schemes (either efficient or not) in the adversarial setting had a rate bounded away from 1, and no nontrivial efficient deterministic coding schemes were known with any constant rate. Essential to both results is an explicit, efficiently encodable and decodable systematic tree code of length n that has relative distance Ω(1/log n ) and rate approaching 1, defined over an O (log n )-bit alphabet. No nontrivial tree code (either efficient or not) was known to approach rate 1, and no nontrivial distance bound was known for any efficient constant rate tree code. The fact that our tree code is systematic, turns out to play an important role in obtaining rate in the random error model, and approaching rate 1 in the adversarial error model.

Details

SODA Conference 2015 Conference Paper

Capacity of Interactive Communication over Erasure Channels and Channels with Feedback

Ran Gelles
Bernhard Haeupler

We consider interactive communication performed over two simple types of noisy channels: binary error channels with noiseless feedback and binary erasure channels. In both cases, the noise model is adversarial Assuming at most ε- fraction of the bits can be corrupted, we show coding schemes that simulate any alternating interactive protocol with rate 1 — Θ( H (ε)). All our simulations are simple, randomized, and computationally efficient. The rates of our coding schemes stand in contrast to the interactive communication rates supported by random or adversarial error channels without feedback, for which the best known coding schemes achieve rates of and, respectively. As these rates are conjectured to be optimal, our result implies a large asymptotic gap between interactive communication rate over noisy channels with and without feedback. Such a gap has no equivalent in the standard one-way communication setting.

Details

TCS Journal 2014 Journal Article

How to catch L 2 -heavy-hitters on sliding windows

Vladimir Braverman
Ran Gelles
Rafail Ostrovsky

Finding heavy-elements (heavy-hitters) in streaming data is one of the central, and well-understood tasks. Despite the importance of this problem, when considering the sliding windows model of streaming (where elements eventually expire) the problem of finding L 2 -heavy elements has remained completely open despite multiple papers and considerable success in finding L 1 -heavy elements. Since the L 2 -heavy element problem doesn't satisfy certain conditions, existing methods for sliding windows algorithms, such as smooth histograms or exponential histograms are not directly applicable to it. In this paper, we develop the first polylogarithmic-memory algorithm for finding L 2 -heavy elements in the sliding window model. Our technique allows us not only to find L 2 -heavy elements, but also heavy elements with respect to any L p with 0 < p ≤ 2 on sliding windows. By this we completely “close the gap” and resolve the question of finding L p -heavy elements in the sliding window model with polylogarithmic memory, since it is well known that for p > 2 this task is impossible. We demonstrate a broader applicability of our method on two additional examples: we show how to obtain a sliding window approximation of the similarity of two streams, and of the fraction of elements that appear exactly a specified number of times within the window (the α-rarity problem). In these two illustrative examples of our method, we replace the current expected memory bounds with worst case bounds.

Details DOI

FOCS Conference 2011 Conference Paper

Efficient and Explicit Coding for Interactive Communication

Ran Gelles
Ankur Moitra
Amit Sahai

We revisit the problem of reliable interactive communication over a noisy channel, and obtain the first fully explicit (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memory less noisy channel with constant capacity, and fails with exponentially small probability in the total length of the protocol. Following a work by Schulman [Schulman 1993] our simulation uses a tree-code, yet as opposed to the non-constructive absolute tree-code used by Schulman, we introduce a relaxation in the notion of goodness for a tree code and define a potent tree code. This relaxation allows us to construct an explicit emulation procedure for any two-party protocol. Our results also extend to the case of interactive multiparty communication. We show that a randomly generated tree code (with suitable constant alphabet size) is an efficiently decodable potent tree code with overwhelming probability. Furthermore we are able to partially derandomize this result by means of epsilon-biased distributions using only O(N) random bits, where N is the depth of the tree.

Details