Search Results

Documents authored by Gelles, Ran

Document
DOI: 10.4230/LIPIcs.DISC.2024.26
Content-Oblivious Leader Election on Rings

Authors: Fabian Frei, Ran Gelles, Ahmed Ghazy, and Alexandre Nolin

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content of all messages across all channels. In a recent work, Censor-Hillel, Cohen, Gelles, and Sela (Distributed Computing, 2023) showed how to perform arbitrary computations in a content-oblivious way in 2-edge connected networks but only if the network has a distinguished node (called root) to initiate the computation. Our goal is to remove this assumption, which was conjectured to be necessary. Achieving this goal essentially reduces to performing a content-oblivious leader election since an elected leader can then serve as the root required to perform arbitrary content-oblivious computations. We focus on ring networks, which are the simplest 2-edge connected graphs. On oriented rings, we obtain a leader election algorithm with message complexity O(n ⋅ ID_max), where ID_max is the maximal assigned ID. As it turns out, this dependency on ID_max is inherent: we show a lower bound of Ω(n log(ID_max/n)) messages for content-oblivious leader election algorithms. We also extend our results to non-oriented rings, where nodes cannot tell which channel leads to which neighbor. In this case, however, the algorithm does not terminate but only reaches quiescence.
Cite as

Fabian Frei, Ran Gelles, Ahmed Ghazy, and Alexandre Nolin. Content-Oblivious Leader Election on Rings. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.DISC.2024.26,
  author =	{Frei, Fabian and Gelles, Ran and Ghazy, Ahmed and Nolin, Alexandre},
  title =	{{Content-Oblivious Leader Election on Rings}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.26},
  URN =		{urn:nbn:de:0030-drops-212527},
  doi =		{10.4230/LIPIcs.DISC.2024.26},
  annote =	{Keywords: Content-Oblivious Computation, Faulty Communication, Leader Election, Ring Networks, Ring Orientation}
}
Document
DOI: 10.4230/LIPIcs.DISC.2024.27
Sorting in One and Two Rounds Using t-Comparators

Authors: Ran Gelles, Zvi Lotker, and Frederik Mallmann-Trenn

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We examine sorting algorithms for n elements whose basic operation is comparing t elements simultaneously (a t-comparator). We focus on algorithms that use only a single round or two rounds - comparisons performed in the second round depend on the outcomes of the first round comparators. Algorithms with a small number of rounds are well-suited to distributed settings in which communication rounds are costly. We design deterministic and randomized algorithms. In the deterministic case, we show an interesting relation to design theory (namely, to 2-Steiner systems), which yields a single-round optimal algorithm for n = t^{2^k} with any k ≥ 1 and a variety of possible values of t. For some values of t, however, no algorithm can reach the optimal (information-theoretic) bound on the number of comparators. For this case (and any other n and t), we show an algorithm that uses at most three times as many comparators as the theoretical bound. We also design a randomized Las-Vegas two-round sorting algorithm for any n and t. Our algorithm uses an asymptotically optimal number of O(max(n^{3/2}/t²,n/t)) comparators, with high probability, i.e., with probability at least 1-1/n. The analysis of this algorithm involves the gradual unveiling of randomness, using a novel technique which we coin the binary tree of deferred randomness.
Cite as

Ran Gelles, Zvi Lotker, and Frederik Mallmann-Trenn. Sorting in One and Two Rounds Using t-Comparators. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gelles_et_al:LIPIcs.DISC.2024.27,
  author =	{Gelles, Ran and Lotker, Zvi and Mallmann-Trenn, Frederik},
  title =	{{Sorting in One and Two Rounds Using t-Comparators}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.27},
  URN =		{urn:nbn:de:0030-drops-212539},
  doi =		{10.4230/LIPIcs.DISC.2024.27},
  annote =	{Keywords: Sorting, Steiner-System, Round Complexity, Deferred Randomness}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.41
Brief Announcement: Towards Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary

Authors: Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We address the problem of Reliable Broadcast in asynchronous message-passing systems with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates an almost optimal amount of O(|m|+n²κ) bits per node, where |m| represents the length of the application message and κ = Ω(log n) is a security parameter. This improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of O(n|m|+n²κ) bits per node. Our solution sends at most 4n² messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message m. Instead, nodes forward authenticated fragments of the encoding of m using an erasure-correcting code. Under the cryptographic assumptions of PKI and collision-resistant hash, and assuming n > 3t+2d, where the adversary drops at most d messages per broadcast, our algorithm allows at least 𝓁 = n - t - (1 + ε)d (for any ε > 0) correct nodes to reconstruct m, despite missing fragments caused by the malicious nodes and the message adversary.
Cite as

Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas. Brief Announcement: Towards Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 41:1-41:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.DISC.2024.41,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Gelles, Ran and Hazay, Carmit and Raynal, Michel and Schiller, Elad Michael and Ta\"{i}ani, Fran\c{c}ois and Zikas, Vassilis},
  title =	{{Brief Announcement: Towards Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{41:1--41:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.41},
  URN =		{urn:nbn:de:0030-drops-212697},
  doi =		{10.4230/LIPIcs.DISC.2024.41},
  annote =	{Keywords: Asynchronous message-passing, Byzantine fault-tolerance, Message adversary, Reliable Broadcast}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.43
Interactive Coding with Unbounded Noise

Authors: Eden Fargion, Ran Gelles, and Meghal Gupta

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
Interactive coding allows two parties to conduct a distributed computation despite noise corrupting a certain fraction of their communication. Dani et al. (Inf. and Comp., 2018) suggested a novel setting in which the amount of noise is unbounded and can significantly exceed the length of the (noise-free) computation. While no solution is possible in the worst case, under the restriction of oblivious noise, Dani et al. designed a coding scheme that succeeds with a polynomially small failure probability. We revisit the question of conducting computations under this harsh type of noise and devise a computationally-efficient coding scheme that guarantees the success of the computation, except with an exponentially small probability. This higher degree of correctness matches the case of coding schemes with a bounded fraction of noise. Our simulation of an N-bit noise-free computation in the presence of T corruptions, communicates an optimal number of O(N+T) bits and succeeds with probability 1-2^(-Ω(N)). We design this coding scheme by introducing an intermediary noise model, where an oblivious adversary can choose the locations of corruptions in a worst-case manner, but the effect of each corruption is random: the noise either flips the transmission with some probability or otherwise erases it. This randomized abstraction turns out to be instrumental in achieving an optimal coding scheme.
Cite as

Eden Fargion, Ran Gelles, and Meghal Gupta. Interactive Coding with Unbounded Noise. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fargion_et_al:LIPIcs.APPROX/RANDOM.2024.43,
  author =	{Fargion, Eden and Gelles, Ran and Gupta, Meghal},
  title =	{{Interactive Coding with Unbounded Noise}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.43},
  URN =		{urn:nbn:de:0030-drops-210361},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.43},
  annote =	{Keywords: Distributed Computation with Noisy Links, Interactive Coding, Noise Resilience, Unbounded Noise, Random Erasure-Flip Noise}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.45
Beeping Shortest Paths via Hypergraph Bipartite Decomposition

Authors: Fabien Dufoulon, Yuval Emek, and Ran Gelles

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in O(D log log n + log³ n) rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in O(D log² n + log³ n) rounds with high probability. Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the hyperedge set of a hypergraph H = (V_H, E_H) into k = Θ (log² n) disjoint subsets F₁ ∪ ⋯ ∪ F_k = E_H such that the (sub-)hypergraph (V_H, F_i) is bipartite in the sense that there exists a vertex subset U ⊆ V such that |U ∩ e| = 1 for every e ∈ F_i. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.
Cite as

Fabien Dufoulon, Yuval Emek, and Ran Gelles. Beeping Shortest Paths via Hypergraph Bipartite Decomposition. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 45:1-45:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dufoulon_et_al:LIPIcs.ITCS.2023.45,
  author =	{Dufoulon, Fabien and Emek, Yuval and Gelles, Ran},
  title =	{{Beeping Shortest Paths via Hypergraph Bipartite Decomposition}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{45:1--45:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.45},
  URN =		{urn:nbn:de:0030-drops-175485},
  doi =		{10.4230/LIPIcs.ITCS.2023.45},
  annote =	{Keywords: Beeping Networks, Shortest Paths, Hypergraph Bipartite Decomposition}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.13
Interactive Coding Resilient to an Unknown Number of Erasures

Authors: Ran Gelles and Siddharth Iyer

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We consider distributed computations between two parties carried out over a noisy channel that may erase messages. Following a noise model proposed by Dani et al. (2018), the noise level observed by the parties during the computation in our setting is arbitrary and a priori unknown to the parties. We develop interactive coding schemes that adapt to the actual level of noise and correctly execute any two-party computation. Namely, in case the channel erases T transmissions, the coding scheme will take N+2T transmissions using an alphabet of size 4 (alternatively, using 2N+4T transmissions over a binary channel) to correctly simulate any binary protocol that takes N transmissions assuming a noiseless channel. We can further reduce the communication to N+T by relaxing the communication model and allowing parties to remain silent rather than forcing them to communicate in every round of the coding scheme. Our coding schemes are efficient, deterministic, have linear overhead both in their communication and round complexity, and succeed (with probability 1) regardless of the number of erasures T.
Cite as

Ran Gelles and Siddharth Iyer. Interactive Coding Resilient to an Unknown Number of Erasures. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gelles_et_al:LIPIcs.OPODIS.2019.13,
  author =	{Gelles, Ran and Iyer, Siddharth},
  title =	{{Interactive Coding Resilient to an Unknown Number of Erasures}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.13},
  URN =		{urn:nbn:de:0030-drops-117999},
  doi =		{10.4230/LIPIcs.OPODIS.2019.13},
  annote =	{Keywords: Interactive coding, erasure channels, distributed computation with noise, unbounded noise}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.10
Optimal Short-Circuit Resilient Formulas

Authors: Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract
We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate’s inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size. Towards our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction 1/5 of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology.
Cite as

Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew. Optimal Short-Circuit Resilient Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.CCC.2019.10,
  author =	{Braverman, Mark and Efremenko, Klim and Gelles, Ran and Yitayew, Michael A.},
  title =	{{Optimal Short-Circuit Resilient Formulas}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.10},
  URN =		{urn:nbn:de:0030-drops-108326},
  doi =		{10.4230/LIPIcs.CCC.2019.10},
  annote =	{Keywords: Circuit Complexity, Noise-Resilient Circuits, Interactive Coding, Coding Theory, Karchmer-Wigderson Games}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.50
Making Asynchronous Distributed Computations Robust to Channel Noise

Authors: Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating a maximal corruption level of \Theta(1/n)-fraction of all messages. Our noise tolerance is optimal and is obtained with only a moderate overhead in the number of messages. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network. Overcoming this more realistic setting of an unknown topology leads to intriguing distributed problems, in which nodes try to learn sufficient information about the network topology in order to perform efficient coding and routing operations for coping with the noise. What makes these problems hard is that these topology exploration computations themselves must already be robust to noise.
Cite as

Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler. Making Asynchronous Distributed Computations Robust to Channel Noise. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ITCS.2018.50,
  author =	{Censor-Hillel, Keren and Gelles, Ran and Haeupler, Bernhard},
  title =	{{Making Asynchronous Distributed Computations Robust to Channel Noise}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.50},
  URN =		{urn:nbn:de:0030-drops-83184},
  doi =		{10.4230/LIPIcs.ITCS.2018.50},
  annote =	{Keywords: Distributed Computation, Coding for Interactive Communication, Noise- Resilient Computation, Coding Theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.21
Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

Authors: Ran Gelles and Yael T. Kalai

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
Multiparty interactive coding allows a network of n parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC’94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of O(log(\Delta + 1)) for networks whose topology has a maximal degree \Delta. Vitally, the communication model in their work forces all the parties to send one message at every round of the protocol, even if they have nothing to send. We re-examine the question of multiparty interactive coding, lifting the requirement that forces all the parties to communicate at each and every round. We use the recently developed information-theoretic machinery of Braverman et al. (STOC ’16) to show that if the network’s topology is a cycle, then there is a specific “cycle task” for which any coding scheme has a communication blowup of \Omega(log n). This is quite surprising since the cycle has a maximal degree of \Delta = 2, implying a coding with a constant blowup when all parties are forced to speak at all rounds. We complement our lower bound with a matching coding scheme for the "cycle task" that has a communication blowup of \Omega(log n). This makes our lower bound for the cycle task tight.
Cite as

Ran Gelles and Yael T. Kalai. Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gelles_et_al:LIPIcs.ITCS.2017.21,
  author =	{Gelles, Ran and T. Kalai, Yael},
  title =	{{Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.21},
  URN =		{urn:nbn:de:0030-drops-81523},
  doi =		{10.4230/LIPIcs.ITCS.2017.21},
  annote =	{Keywords: Interactive Communication, Coding, Stochastic Noise, Communication Complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.61
Coding for Interactive Communication Correcting Insertions and Deletions

Authors: Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties "out of sync", so that there is no consensus regarding the current round of the protocol. In this more general noise model, we obtain the first interactive coding scheme that has a constant rate and tolerates noise rates of up to 1/18 - epsilon. To this end we develop a novel primitive we name edit distance tree code. The edit distance tree code is designed to replace the Hamming distance constraints in Schulman's tree codes (STOC 93), with a stronger edit distance requirement. However, the straightforward generalization of tree codes to edit distance does not seem to yield a primitive that suffices for communication in the presence of synchronization problems. Giving the "right" definition of edit distance tree codes is a main conceptual contribution of this work.
Cite as

Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky. Coding for Interactive Communication Correcting Insertions and Deletions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.ICALP.2016.61,
  author =	{Braverman, Mark and Gelles, Ran and Mao, Jieming and Ostrovsky, Rafail},
  title =	{{Coding for Interactive Communication Correcting Insertions and Deletions}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.61},
  URN =		{urn:nbn:de:0030-drops-61981},
  doi =		{10.4230/LIPIcs.ICALP.2016.61},
  annote =	{Keywords: Interactive communication, coding, edit distance}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact