Explicit Extremal Designs and Applications to Extractors
Explicit Extremal Designs and Applications to Extractors
复制标题
显式极值设计及其在提取器中的应用
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
J. Goodman
中科院分区：
文献类型：
--
作者：
Eshan Chattopadhyay;J. Goodman
一个$（n，r，s）$-设计或$（n，r，s）$-部分Steiner系统是一个$r$-一致超图，其顶点数为$n$，其两两超边交的大小为$<s$。一个超图G$中的独立集是一个不覆盖任何超边的顶点子集，它的独立数$alpha（G）$是它的最大独立集的大小。对于所有的常数$rgeq sinmathbb{N}$，$r$ even，我们显式构造了$（n，r，s）$-设计$（G_n）_{nmathbb {N}}$，其独立数$alpha（G_n）leq O（n^{frac{2（r-s）}{r}}）$。这给出了Rodl和Sinajova（Random Structures & Algorithms，1994）的结果的第一个去随机化。
通过将我们的设计与最近明确构建的适用于低熵的泄漏弹性提取器相结合（Chattopadhyay等人，FOCS 2020），我们获得了简单且显着改进的对抗性和小空间源的低错误显式提取器。特别地，对于任何常数$delta>0$，我们从$（N，K，n，k）$中提取出局部性为0 $的对抗源，其中$Kgeq N^delta$和$kgeq ext{polylog }n$。先前的最佳结果（Chattopadhyay等人，STOC 2020）要求$Kgeq N^{1/2+o（1）}$。结果，我们得到了超过$n$比特的小空间源的提取器，熵要求为$kgeq n^{1/2+delta}$，而之前的最佳结果（Chattopadhyay等人，STOC 2020）要求$kgeq n^{2/3+delta}$。
An $(n,r,s)$-design, or $(n,r,s)$-partial Steiner system, is an $r$-uniform hypergraph over $n$ vertices with pairwise hyperedge intersections of size $<s$. An independent set in a hypergraph $G$ is a subset of vertices covering no hyperedge, and its independence number $alpha(G)$ is the size of its largest independent set. For all constants $rgeq sinmathbb{N}$ with $r$ even, we explicitly construct $(n,r,s)$-designs $(G_n)_{ninmathbb{N}}$ with independence number $alpha(G_n)leq O(n^{frac{2(r-s)}{r}})$. This gives the first derandomization of a result by Rodl and Sinajova (Random Structures & Algorithms, 1994).
By combining our designs with a recent explicit construction of a leakage-resilient extractor that works for low-entropy (Chattopadhyay et al., FOCS 2020), we obtain simple and significantly improved low-error explicit extractors for adversarial and small-space sources. In particular, for any constant $delta>0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $Kgeq N^delta$ and $kgeq ext{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $Kgeq N^{1/2+o(1)}$. As a result, we get extractors for small-space sources over $n$ bits with entropy requirement $kgeq n^{1/2+delta}$, whereas the previous best result (Chattopadhyay et al., STOC 2020) required $kgeq n^{2/3+delta}$.
针对有限共谋协议的提取器和秘密共享
DOI：
10.1109/focs46700.2020.00117
发表时间：
2020
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Chattopadhyay, Eshan;Goodman, Jesse;Goyal, Vipul;Kumar, Ashutosh;Li, Xin;Meka, Raghu;Zuckerman, David
通讯作者：
Zuckerman, David