Extractors for sum of two sources
Extractors for sum of two sources
复制标题
两个来源之和的提取器
DOI：
10.1145/3519935.3519963
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Liao, Jyun-Jie
中科院分区：
文献类型：
--
作者：
Chattopadhyay, Eshan;Liao, Jyun-Jie
我们考虑从和集源中提取随机性的问题，和集源是Chattopadhyay和Li（STOC，2016）引入的一类一般弱源。一个（n，k，C）-和集源X是{0，1} n上的一个分布，其形式为X1 +X2+...+XC，其中Xi是n位的独立源，最小熵至少为k。以往的提取器要么要求源的个数C是一个大的常数，要么要求最小熵k至少为0.51n.作为我们的主要结果，我们构造了一个和集源的显式提取器，当C =2，最小熵poly（logn）和多项式小误差时.我们可以进一步提高最小熵的要求（logn）·（loglogn）1 +o（1），代价是我们的提取器的误差参数变差。我们发现我们的和集提取器的应用程序提取随机性从其他良好的研究模型的弱源，如仿射源，小空间源，和交错sources.Interestingly，它是未知的，如果一个随机函数是一个提取器和集源。我们使用加法组合学的技术来证明它是一个分散器，并进一步证明仿射提取器适用于一个有趣的和集源子类，该子类非正式地对应于“低倍”情况（即，X1 + X2的支集不大于2k）。
We consider the problem of extracting randomness fromsumset sources, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n,k,C)-sumset sourceXis a distribution on {0,1}nof the formX1+X2+ … +XC, whereXi’s are independent sources onnbits with min-entropy at leastk. Prior extractors either required the number of sourcesCto be a large constant or the min-entropykto be at least 0.51n.As our main result, we construct an explicit extractor for sumset sources in the setting ofC=2 for min-entropypoly(logn) and polynomially small error. We can further improve the min-entropy requirement to (logn) · (loglogn)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 ofX1+X2is not much larger than 2k).
登录
查看更多内容
低权重仿射源提取器
DOI：
10.1109/ccc.2009.36
发表时间：
2009
期刊：
2009 24th Annual IEEE Conference on Computational Complexity
影响因子：
--
作者：
Anup Rao
通讯作者：
Anup Rao
DOI：
10.1109/focs.2016.27
发表时间：
2016
期刊：
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Gil Cohen;L. Schulman
通讯作者：
L. Schulman
任意阿贝尔群中的弗雷曼定理
DOI：
10.1112/jlms/jdl021
发表时间：
2005
期刊：
Journal of the London Mathematical Society
影响因子：
--
作者：
B. Green;I. Ruzsa
通讯作者：
I. Ruzsa
从双源提取器到不可延展提取器的有效减少：实现接近对数的最小熵
DOI：
10.1145/3055399.3055423
发表时间：
2017
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Avraham Ben;Dean Doron;A. Ta
通讯作者：
A. Ta
用于交错篡改和篡改组合的不可延展代码、提取器和秘密共享
DOI：
10.1007/978-3-030-64381-2_21
发表时间：
2020
期刊：
Cham
影响因子：
--
作者：
Chattopadhyay, Eshan;Li, Xin
通讯作者：
Li, Xin