Schloss Dagstuhl - Leibniz-Zentrum fΓΌr Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fΓΌr Informatik GmbH scholarly article en Doron, Dean; Wootters, Mary https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-163961
URL:

;

High-Probability List-Recovery, and Applications to Heavy Hitters

pdf-format:


Abstract

An error correcting code π’ž : Ξ£^k β†’ Σⁿ is efficiently list-recoverable from input list size 𝓁 if for any sets ℒ₁, …, β„’_n βŠ† Ξ£ of size at most 𝓁, one can efficiently recover the list β„’ = {x ∈ Ξ£^k : βˆ€ j ∈ [n], π’ž(x)_j ∈ β„’_j}. While list-recovery has been well-studied in error correcting codes, all known constructions with "efficient" algorithms are not efficient in the parameter 𝓁. In this work, motivated by applications in algorithm design and pseudorandomness, we study list-recovery with the goal of obtaining a good dependence on 𝓁. We make a step towards this goal by obtaining it in the weaker case where we allow a randomized encoding map and a small failure probability, and where the input lists are derived from unions of codewords. As an application of our construction, we give a data structure for the heavy hitters problem in the strict turnstile model that, for some parameter regimes, obtains stronger guarantees than known constructions.

BibTeX - Entry

@InProceedings{doron_et_al:LIPIcs.ICALP.2022.55,
  author =	{Doron, Dean and Wootters, Mary},
  title =	{{High-Probability List-Recovery, and Applications to Heavy Hitters}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{55:1--55: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/opus/volltexte/2022/16396},
  URN =		{urn:nbn:de:0030-drops-163961},
  doi =		{10.4230/LIPIcs.ICALP.2022.55},
  annote =	{Keywords: List recoverable codes, Heavy Hitters, high-dimensional expanders}
}

Keywords: List recoverable codes, Heavy Hitters, high-dimensional expanders
Seminar: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue date: 2022
Date of publication: 28.06.2022


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