Search Results

Documents authored by Rubinstein, Ittai

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.102
Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem

Authors: Ittai Rubinstein

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In the trace reconstruction problem, one is given many outputs (called traces) of a noise channel applied to the same input message x, and is asked to recover the input message. Common noise channels studied in the context of trace reconstruction include the deletion channel which deletes each bit w.p. δ, the insertion channel which inserts a G_j i.i.d. uniformly distributed bits before each bit of the input message (where G_j is i.i.d. geometrically distributed with parameter σ) and the symmetry channel which flips each bit of the input message i.i.d. w.p. γ. De et al. and Nazarov and Peres [De et al., 2017; Nazarov and Peres, 2017] showed that any string x can be reconstructed from exp(O(n^{1/3})) traces. Holden et al. [Holden et al., 2018] adapted the techniques used to prove this upper bound, to construct an algorithm for average-case trace reconstruction from the insertion-deletion channel with a sample complexity of exp(O(log^{1/3} n)). However, it is not clear how to apply their techniques more generally and in particular for the recent worst-case upper bound of exp(Õ(n^{1/5})) shown by Chase [Chase, 2021] for the deletion channel. We prove a general reduction from the average-case to smaller instances of a problem similar to worst-case and extend Chase’s upper-bound to this problem and to symmetry and insertion channels as well. Using this reduction and generalization of Chase’s bound, we introduce an algorithm for the average-case trace reconstruction from the symmetry-insertion-deletion channel with a sample complexity of exp(Õ(log^{1/5} n)).
Cite as

Ittai Rubinstein. Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rubinstein:LIPIcs.ICALP.2023.102,
  author =	{Rubinstein, Ittai},
  title =	{{Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{102:1--102:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.102},
  URN =		{urn:nbn:de:0030-drops-181542},
  doi =		{10.4230/LIPIcs.ICALP.2023.102},
  annote =	{Keywords: Trace Reconstruction, Synchronization Channels, Computational Learning Theory, Computational Biology}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.105
Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel

Authors: Ittai Rubinstein

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Two of the most common models for channels with synchronisation errors are the Binary Deletion Channel with parameter p (BDC_p) - a channel where every bit of the codeword is deleted i.i.d with probability p, and the Poisson Repeat Channel with parameter λ (PRC_λ) - a channel where every bit of the codeword is repeated Poisson(λ) times. Previous constructions based on synchronisation strings yielded codes with rates far lower than the capacities of these channels [Con and Shpilka, 2019; Guruswami and Li, 2018], and the only efficient construction to achieve capacity on the BDC at the time of writing this paper is based on the far more advanced methods of polar codes [Tal et al., 2021]. In this work, we present a new method for concatenating synchronisation codes and use it to construct simple and efficient encoding and decoding algorithms for both channels with nearly optimal rates.
Cite as

Ittai Rubinstein. Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 105:1-105:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rubinstein:LIPIcs.ICALP.2022.105,
  author =	{Rubinstein, Ittai},
  title =	{{Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{105:1--105:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.105},
  URN =		{urn:nbn:de:0030-drops-164466},
  doi =		{10.4230/LIPIcs.ICALP.2022.105},
  annote =	{Keywords: Error Correcting Codes, Algorithmic Coding Theory, Binary Deletion Channel}
}
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