ECCC-Report TR21-147https://eccc.weizmann.ac.il/report/2021/147Comments and Revisions published for TR21-147en-usMon, 25 Oct 2021 08:27:47 +0300
Revision 1
| Extractors for Sum of Two Sources |
Jyun-Jie Liao,
Eshan Chattopadhyay
https://eccc.weizmann.ac.il/report/2021/147#revision1We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An $(n,k,C)$-sumset source $\mathbf{X}$ is a distribution on $\{0,1\}^n$ of the form $\mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C$, where $\mathbf{X}_i$'s are independent sources on $n$ bits with min-entropy at least $k$. Prior extractors either required the number of sources $C$ to be a large constant or the min-entropy $k$ to be at least $0.51 n$.
As our main result, we construct an explicit extractor for sumset sources in the setting of $C=2$ for min-entropy $\mathrm{poly}(\log n)$ and polynomially small error. We can further improve the min-entropy requirement to $(\log n) \cdot (\log \log n)^{1 + o(1)}$ at the expense of worse error parameter of our extractor. We find applications of our sumset extractor for extracting randomness from other well-studied models of weak sources such as affine sources, small-space sources, and interleaved sources.
Interestingly, it is unknown if a random function is an extractor for sumset sources. We use techniques from additive combinatorics to show that it is a disperser, and further prove that an affine extractor works for an interesting subclass of sumset sources which informally corresponds to the ``low doubling" case
(i.e., the support of $\mathbf{X_1} + \mathbf{X_2}$ is not much larger than $2^k$).Mon, 25 Oct 2021 08:27:47 +0300https://eccc.weizmann.ac.il/report/2021/147#revision1
Paper TR21-147
| Extractors for Sum of Two Sources |
Jyun-Jie Liao,
Eshan Chattopadhyay
https://eccc.weizmann.ac.il/report/2021/147We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An $(n,k,C)$-sumset source $\mathbf{X}$ is a distribution on $\{0,1\}^n$ of the form $\mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C$, where $\mathbf{X}_i$'s are independent sources on $n$ bits with min-entropy at least $k$. Prior extractors either required the number of sources $C$ to be a large constant or the min-entropy $k$ to be at least $0.51 n$.
As our main result, we construct an explicit extractor for sumset sources in the setting of $C=2$ for min-entropy $\mathrm{poly}(\log n)$ and polynomially small error. We can further improve the min-entropy requirement to $(\log n) \cdot (\log \log n)^{1 + o(1)}$ at the expense of worse error parameter of our extractor. We find applications of our sumset extractor for extracting randomness from other well-studied models of weak sources such as affine sources, small-space sources, and interleaved sources. Sun, 24 Oct 2021 14:46:03 +0300https://eccc.weizmann.ac.il/report/2021/147