Search Results

Documents authored by Gupta, Meghal

Document
DOI: 10.4230/LIPIcs.CCC.2025.13
Tight Bounds for Stream Decodable Error-Correcting Codes

Authors: Meghal Gupta, Venkatesan Guruswami, and Mihir Singhal

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
In order to communicate a message over a noisy channel, a sender (Alice) uses an error-correcting code to encode her message, a bitstring x, into a codeword. The receiver (Bob) decodes x correctly whenever there is at most a small constant fraction of adversarial errors in the transmitted codeword. We investigate the setting where Bob is restricted to be a low-space streaming algorithm. Specifically, Bob receives the message as a stream and must process it and write x in order to a write-only tape while using low (say polylogarithmic) space. Note that such a primitive then allows the execution of any downstream streaming computation on x. We show three basic results about this setting, which are informally as follows: [(i)] 1) There is a stream decodable code of near-quadratic length, resilient to error-fractions approaching the optimal bound of 1/4. 2) There is no stream decodable code of sub-quadratic length, even to correct any small constant fraction of errors. 3) If Bob need only compute a private linear function of the bits of x, instead of writing them all to the output tape, there is a stream decodable code of near-linear length. Our constructions use locally decodable codes with additional functionality in the decoding, and (for the result on linear functions) repeated tensoring. Our lower bound, which rather surprisingly demonstrates a strong information-theoretic limitation originating from a computational restriction, proceeds via careful control of the message indices that may be output during successive blocks of the stream, a task complicated by the arbitrary state of the decoder during the algorithm.
Cite as

Meghal Gupta, Venkatesan Guruswami, and Mihir Singhal. Tight Bounds for Stream Decodable Error-Correcting Codes. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.CCC.2025.13,
  author =	{Gupta, Meghal and Guruswami, Venkatesan and Singhal, Mihir},
  title =	{{Tight Bounds for Stream Decodable Error-Correcting Codes}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.13},
  URN =		{urn:nbn:de:0030-drops-237072},
  doi =		{10.4230/LIPIcs.CCC.2025.13},
  annote =	{Keywords: Coding theory, Streaming computation, Locally decodable code, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.59
Error Correction for Message Streams

Authors: Meghal Gupta and Rachel Yun Zhang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In the setting of error correcting codes, Alice wants to send a message x ∈ {0,1}ⁿ to Bob via an encoding enc(x) that is resilient to error. In this work, we investigate the scenario where Bob is a low space decoder. More precisely, he receives Alice’s encoding enc(x) bit-by-bit and desires to compute some function f(x) in low space. A generic error-correcting code does not accomplish this because decoding is a very global process and requires at least linear space. Locally decodable codes partially solve this problem as they allow Bob to learn a given bit of x in low space, but not compute a generic function f. Our main result is an encoding and decoding procedure where Bob is still able to compute any such function f in low space when a constant fraction of the stream is corrupted. More precisely, we describe an encoding function enc(x) of length poly(n) so that for any decoder (streaming algorithm) A that on input x computes f(x) in space s, there is an explicit decoder B that computes f(x) in space s ⋅ polylog(n) as long as there were not more than 1/4 - ε fraction of (adversarial) errors in the input stream enc(x).
Cite as

Meghal Gupta and Rachel Yun Zhang. Error Correction for Message Streams. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ITCS.2025.59,
  author =	{Gupta, Meghal and Zhang, Rachel Yun},
  title =	{{Error Correction for Message Streams}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.59},
  URN =		{urn:nbn:de:0030-drops-226875},
  doi =		{10.4230/LIPIcs.ITCS.2025.59},
  annote =	{Keywords: error-correcting codes, streaming algorithms, space-efficient algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.60
List Decoding Bounds for Binary Codes with Noiseless Feedback

Authors: Meghal Gupta and Rachel Yun Zhang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In an error-correcting code, a sender encodes a message x ∈ {0, 1}^k such that it is still decodable by a receiver on the other end of a noisy channel. In the setting of error-correcting codes with feedback, after sending each bit, the sender learns what was received at the other end and can tailor future messages accordingly. While the unique decoding radius of feedback codes has long been known to be 1/3, the list decoding capabilities of feedback codes is not well understood. In this paper, we provide the first nontrivial bounds on the list decoding radius of feedback codes for lists of size 𝓁. For 𝓁 = 2, we fully determine the 2-list decoding radius to be 3/7. For larger values of 𝓁, we show an upper bound of 1/2 - 1/{2^(𝓁+2) - 2}, and show that the same techniques for the 𝓁 = 2 case cannot match this upper bound in general.
Cite as

Meghal Gupta and Rachel Yun Zhang. List Decoding Bounds for Binary Codes with Noiseless Feedback. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 60:1-60:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ITCS.2025.60,
  author =	{Gupta, Meghal and Zhang, Rachel Yun},
  title =	{{List Decoding Bounds for Binary Codes with Noiseless Feedback}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{60:1--60:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.60},
  URN =		{urn:nbn:de:0030-drops-226880},
  doi =		{10.4230/LIPIcs.ITCS.2025.60},
  annote =	{Keywords: error-correcting codes, feedback, list decoding}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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