License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.32
URN: urn:nbn:de:0030-drops-188576
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18857/
Go to the corresponding LIPIcs Volume Portal

Gupta, Meghal ; Zhang, Rachel Yun

Interactive Error Correcting Codes: New Constructions and Impossibility Bounds

pdf-format:
LIPIcs-APPROX32.pdf (0.8 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2023/18857},
  URN =		{urn:nbn:de:0030-drops-188576},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.32},
  annote =	{Keywords: Code, Interactive Protocol, Error Resilience}
}

Keywords: Code, Interactive Protocol, Error Resilience
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI