ECCC-Report TR20-162https://eccc.weizmann.ac.il/report/2020/162Comments and Revisions published for TR20-162en-usThu, 12 Nov 2020 23:47:46 +0200
Revision 1
| High-Probability List-Recovery, and Applications to Heavy Hitters |
Dean Doron,
Mary Wootters
https://eccc.weizmann.ac.il/report/2020/162#revision1An error correcting code $\mathcal{C} \colon \Sigma^k \to \Sigma^n$ is list-recoverable from input list size $\ell$ if for any sets $\mathcal{L}_1, \ldots, \mathcal{L}_n \subseteq \Sigma$ of size at most $\ell$, one can efficiently recover the list $\mathcal{L} = \{ x \in \Sigma^k : \forall j \in [n], \mathcal{C}(x)_j \in \mathcal{L}_j \}$. While list-recovery has been well-studied in error correcting codes, all known constructions with "efficient" algorithms are not efficient in the parameter $\ell$. In this work, motivated by applications in algorithm design and pseudorandomness, we study list-recovery with the goal of obtaining a good dependence on $\ell$. 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.Thu, 12 Nov 2020 23:47:46 +0200https://eccc.weizmann.ac.il/report/2020/162#revision1
Paper TR20-162
| High-Probability List-Recovery, and Applications to Heavy Hitters |
Dean Doron,
Mary Wootters
https://eccc.weizmann.ac.il/report/2020/162An error correcting code $\mathcal{C} \colon \Sigma^k \to \Sigma^n$ is list-recoverable from input list size $\ell$ if for any sets $\mathcal{L}_1, \ldots, \mathcal{L}_n \subseteq \Sigma$ of size at most $\ell$, one can efficiently recover the list $\mathcal{L} = \{ x \in \Sigma^k : \forall j \in [n], \mathcal{C}(x)_j \in \mathcal{L}_j \}$. While list-recovery has been well-studied in error correcting codes, all known constructions with "efficient" algorithms are not efficient in the parameter $\ell$. In this work, motivated by applications in algorithm design and pseudorandomness, we study list-recovery with the goal of obtaining a good dependence on $\ell$. 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.Sun, 08 Nov 2020 13:06:59 +0200https://eccc.weizmann.ac.il/report/2020/162