Search Results

Documents authored by Gupta, Meghal

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
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.32
Interactive Error Correcting Codes: New Constructions and Impossibility Bounds

Authors: Meghal Gupta and Rachel Yun Zhang

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

Abstract
An interactive error correcting code (iECC) is an interactive protocol with the guarantee that the receiver can correctly determine the sender’s message, even in the presence of noise. It was shown in works by Gupta, Kalai, and Zhang (STOC 2022) and by Efremenko, Kol, Saxena, and Zhang (FOCS 2022) that there exist iECC’s that are resilient to a larger fraction of errors than is possible in standard error-correcting codes without interaction. In this work, we improve upon these existing works in two ways: - First, we improve upon the erasure iECC of Kalai, Gupta, and Zhang, which has communication complexity quadratic in the message size. In our work, we construct the first iECC resilient to > 1/2 adversarial erasures that is also positive rate. For any ε > 0, our iECC is resilient to 6/11 - ε adversarial erasures and has size O_ε(k). - Second, we prove a better upper bound on the maximal possible error resilience of any iECC in the case of bit flip errors. It is known that an iECC can achieve 1/4 + 10^{-5} error resilience (Efremenko, Kol, Saxena, and Zhang), while the best known upper bound was 2/7 ≈ 0.2857 (Gupta, Kalai, and Zhang). We improve upon the upper bound, showing that no iECC can be resilient to more than 13/47 ≈ 0.2766 fraction of errors.
Cite as

Meghal Gupta and Rachel Yun Zhang. Interactive Error Correcting Codes: New Constructions and Impossibility Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.APPROX/RANDOM.2023.32,
  author =	{Gupta, Meghal and Zhang, Rachel Yun},
  title =	{{Interactive Error Correcting Codes: New Constructions and Impossibility Bounds}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.32},
  URN =		{urn:nbn:de:0030-drops-188576},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.32},
  annote =	{Keywords: Code, Interactive Protocol, Error Resilience}
}
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