Extractors for sum of two sources

DOI10.1145/3519935.3519963MaRDI QIDQ6083614zbMATH OpenOpenAlexFDO

Authors Eshan Chattopadhyay, Jyun-Jie Liao

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.12652

zbMATH Keywords

extractors sumsets correlation breakers small-space sources

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We consider the problem of extracting randomness from extit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An

(n, k, C)

-sumset source

m a t h b f X

is a distribution on

{0, 1}^{n}

of the form

m a t h b f X_{1} + m a t h b f X_{2} + l d o t s + m a t h b f X_{C}

, where

m a t h b f 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

m a t h r m p o l y (l o g n)

and polynomially small error. We can further improve the min-entropy requirement to

(l o g n) c d o t (l o g l o g 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

m a t h b f X_{1} + m a t h b f X_{2}

is not much larger than

2^{k}

).

Recommendations

Cited in

(4)

This page was built for publication: Extractors for sum of two sources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083614)