Document Open Access Logo

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

Authors Dean Doron , Mary Wootters

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.55.pdf
  • Filesize: 0.79 MB
  • 17 pages

Document Identifiers

Author Details

Dean Doron
  • Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Mary Wootters
  • Departments of Computer Science and Electrical Engineering, Stanford University, CA, USA

Funding

  • Doron, Dean: The work was done at Stanford, supported by NSF award CCF-1763311.
  • Wootters, Mary: Supported by NSF award CCF-1844628 and NSF-BSF award CCF-1814629.

Acknowledgements

We would like to thank Jelani Nelson and Amnon Ta-Shma for helpful conversations. We thank Mahdi Cheraghchi, Venkat Guruswami, and Badih Ghazi for pointing out relevant related work. We also thank anonymous reviewers for helpful comments and for pointing out related works.

Cite AsGet BibTex

Dean Doron and Mary Wootters. High-Probability List-Recovery, and Applications to Heavy Hitters. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.55

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • List recoverable codes
  • Heavy Hitters
  • high-dimensional expanders

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on information theory, 38(2):509-516, 1992. Google Scholar
  2. Noga Alon, Jeff Edmonds, and Michael Luby. Linear time erasure codes with nearly optimal recovery. In 36th Annual Symposium on Foundations of Computer Science (FOCS 1995), pages 512-519. IEEE, 1995. Google Scholar
  3. Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Near-optimal erasure list-decodable codes. In 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  4. Mark Bun, Jelani Nelson, and Uri Stemmer. Heavy hitters and the structure of local privacy. ACM Transactions on Algorithms (TALG), 15(4):1-40, 2019. Google Scholar
  5. Mahdi Cheraghchi and Vasileios Nakos. Combinatorial group testing and sparse recovery schemes with near-optimal decoding time. In 61st Annual Symposium on Foundations of Computer Science (FOCS 2020). IEEE, 2020. To appear. Google Scholar
  6. Graham Cormode and Marios Hadjieleftheriou. Methods for finding frequent items in data streams. The VLDB Journal, 19(1):3-20, 2010. Google Scholar
  7. Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58-75, 2005. Google Scholar
  8. Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi. Locally testable codes via high-dimensional expanders. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.01045.
  9. Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-Shma. List decoding with double samplers. In ACM-SIAM 38th Annual Symposium on Discrete Algorithms (SODA 2019), pages 2134-2153. SIAM, 2019. Google Scholar
  10. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Nearly optimal pseudorandomness from hardness. In 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 1057-1068. IEEE, 2020. Google Scholar
  11. Dean Doron and Mary Wootters. High-probability list-recovery, and applications to heavy hitters. In Electronic Colloquium on Computational Complexity (ECCC), 2021. Manuscript. Google Scholar
  12. Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss. For-all sparse recovery in near-optimal time. ACM Transactions on Algorithms (TALG), 13(3):1-26, 2017. Google Scholar
  13. Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, and Martin J. Strauss. 𝓁₂/𝓁₂-foreach sparse recovery with low risk. In International Colloquium on Automata, Languages, and Programming (ICALP 2013), pages 461-472. Springer, 2013. Google Scholar
  14. Venkatesan Guruswami and Piotr Indyk. Linear-time list decoding in error-free settings. In International Colloquium on Automata, Languages, and Programming (ICALP 2004), pages 695-707. Springer, 2004. Google Scholar
  15. Venkatesan Guruswami and Swastik Kopparty. Explicit subspace designs. Combinatorica, 36(2):161-185, 2016. Google Scholar
  16. Venkatesan Guruswami and Atri Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory, 54(1):135-150, 2008. Google Scholar
  17. Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. In 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pages 28-37. IEEE, 1998. Google Scholar
  18. Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. Journal of the ACM (JACM), 56(4):1-34, 2009. Google Scholar
  19. Venkatesan Guruswami and Carol Wang. Linear-algebraic list decoding for variants of reed-solomon codes. IEEE Transactions on Information Theory, 59(6):3257-3268, 2013. Google Scholar
  20. Venkatesan Guruswami and Chaoping Xing. Folded codes from function field towers and improved optimal rate list decoding. In 44th Annual Symposium on Theory of Computing (STOC 2012), pages 339-350. ACM, 2012. Google Scholar
  21. Venkatesan Guruswami and Chaoping Xing. List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound. In 45th Annual Symposium on Theory of Computing (STOC 2012), pages 843-852. ACM, 2013. Google Scholar
  22. Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. Local list recovery of high-rate tensor codes and applications. SIAM Journal on Computing, pages FOCS17-157, 2019. Google Scholar
  23. Brett Hemenway and Mary Wootters. Linear-time list recovery of high-rate expander codes. Information and Computation, 261:202-218, 2018. Google Scholar
  24. Piotr Indyk, Hung Q. Ngo, and Atri Rudra. Efficiently decodable non-adaptive group testing. In ACM-SIAM 21st Annual Symposium on Discrete Algorithms (SODA 2010), pages 1126-1142. SIAM, 2010. Google Scholar
  25. Hossein Jowhari, Mert Sağlam, and Gábor Tardos. Tight bounds for 𝓁_p samplers, finding duplicates in streams, and related problems. In ACM SIGMOD-SIGACT-SIGART 30th Annual Symposium on Principles of Database Systems, pages 49-58, 2011. Google Scholar
  26. William Kautz and Roy Singleton. Nonrandom binary superimposed codes. IEEE Transactions on Information Theory, 10(4):363-377, 1964. Google Scholar
  27. Swastik Kopparty. List-decoding multiplicity codes. Theory of Computing, 11(1):149-182, 2015. Google Scholar
  28. Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, and Mary Wootters. Improved decoding of folded Reed-Solomon and multiplicity codes. In 59th Annual Symposium on Foundations of Computer Science (FOCS 2018), pages 212-223. IEEE, 2018. Google Scholar
  29. Kasper Green Larsen, Jelani Nelson, Huy L. Nguyễn, and Mikkel Thorup. Heavy hitters via cluster-preserving clustering. In 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), pages 61-70. IEEE, 2016. Google Scholar
  30. Kasper Green Larsen, Jelani Nelson, Huy L. Nguyễn, and Mikkel Thorup. Heavy hitters via cluster-preserving clustering. arxiv:1604.01357 [cs.DS], 2016. Google Scholar
  31. Yi Li, Vasileios Nakos, and David P. Woodruff. On low-risk heavy hitters and sparse recovery schemes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116, pages 19:1-19:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018. Google Scholar
  32. Jayadev Misra and David Gries. Finding repeated elements. Science of computer programming, 2(2):143-152, 1982. Google Scholar
  33. Jelani Nelson, Huy L. Nguyễn, and David P. Woodruff. On deterministic sketching and streaming for sparse recovery and norm estimation. Linear Algebra and its Applications, 441:152-167, 2014. Google Scholar
  34. Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms. Journal of the ACM (JACM), 65(3):1-40, 2018. Google Scholar
  35. Hung Q. Ngo, Ely Porat, and Atri Rudra. Efficiently decodable error-correcting list disjunct matrices and applications. In International Colloquium on Automata, Languages, and Programming (ICALP 2011), pages 557-568. Springer, 2011. Google Scholar
  36. Hung Q. Ngo, Ely Porat, and Atri Rudra. Efficiently decodable compressed sensing by list-recoverable codes and recursion. In 29th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2012), volume 14, pages 230-241. LIPIcs, 2012. Google Scholar
  37. Eric Price and Jonathan Scarlett. A fast binary splitting approach to non-adaptive group testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  38. Ran Raz and Omer Reingold. On recycling the randomness of states in space bounded computation. In 31st Annual Symposium on Theory of Computing (STOC 1999), pages 159-168, 1999. Google Scholar
  39. Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996. Google Scholar
  40. Amnon Ta-Shma and David Zuckerman. Extractor codes. IEEE Transactions on Information Theory, 50(12):3015-3025, 2004. Google Scholar
  41. Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM (JACM), 48(4):860-879, 2001. Google Scholar
  42. Gillés Zémor. On expander codes. IEEE Transactions on Information Theory, 47(2):835-837, 2001. Google Scholar
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 Imprint Privacy Contact