ECCC-Report TR20-106https://eccc.weizmann.ac.il/report/2020/106Comments and Revisions published for TR20-106en-usWed, 15 Jul 2020 19:51:41 +0300
Revision 3
| Explicit Extremal Designs and Applications to Extractors |
Eshan Chattopadhyay,
Jesse Goodman
https://eccc.weizmann.ac.il/report/2020/106#revision3An $(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 less than $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 $r\geq s\in\mathbb{N}$ with $r$ even, we explicitly construct $(n,r,s)$-designs $(G_n)_{n\in\mathbb{N}}$ with independence number $\alpha(G_n)\leq O(n^{\frac{2(r-s)}{r}})$. This gives the first derandomization of a result by Rödl and Šinajová (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 $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we get extractors for small-space sources over $n$ bits with entropy requirement $k\geq n^{1/2+\delta}$, whereas the previous best result (Chattopadhyay et al., STOC 2020) required $k\geq n^{2/3+\delta}$.
Wed, 15 Jul 2020 19:51:41 +0300https://eccc.weizmann.ac.il/report/2020/106#revision3
Revision 2
| Explicit Extremal Designs and Applications to Extractors |
Eshan Chattopadhyay,
Jesse Goodman
https://eccc.weizmann.ac.il/report/2020/106#revision2An $(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 $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we get extractors for small-space sources over $n$ bits with entropy requirement $k\geq n^{1/2+\delta}$, whereas the previous best result (Chattopadhyay et al., STOC 2020) required $k\geq n^{2/3+\delta}$.Wed, 15 Jul 2020 19:38:53 +0300https://eccc.weizmann.ac.il/report/2020/106#revision2
Revision 1
| Explicit Extremal Designs and Applications to Extractors |
Eshan Chattopadhyay,
Jesse Goodman
https://eccc.weizmann.ac.il/report/2020/106#revision1An $(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 $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we get extractors for small-space sources over $n$ bits with entropy requirement $k\geq n^{1/2+\delta}$, whereas the previous best result (Chattopadhyay et al., STOC 2020) required $k\geq n^{2/3+\delta}$.Wed, 15 Jul 2020 19:32:53 +0300https://eccc.weizmann.ac.il/report/2020/106#revision1
Paper TR20-106
| Explicit Extremal Designs and Applications to Extractors |
Eshan Chattopadhyay,
Jesse Goodman
https://eccc.weizmann.ac.il/report/2020/106An $(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 $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we get extractors for small-space sources over $n$ bits with entropy requirement $k\geq n^{1/2+\delta}$, whereas the previous best result (Chattopadhyay et al., STOC 2020) required $k\geq n^{2/3+\delta}$.Wed, 15 Jul 2020 19:25:04 +0300https://eccc.weizmann.ac.il/report/2020/106