Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR20-106 | 15th July 2020 19:51

Explicit Extremal Designs and Applications to Extractors

RSS-Feed




Revision #3
Authors: Eshan Chattopadhyay, Jesse Goodman
Accepted on: 15th July 2020 19:51
Downloads: 196
Keywords: 


Abstract:

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 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}$.



Changes to previous version:

Fixed abstract


Revision #2 to TR20-106 | 15th July 2020 19:38

Explicit Extremal Designs and Applications to Extractors





Revision #2
Authors: Eshan Chattopadhyay, Jesse Goodman
Accepted on: 15th July 2020 19:38
Downloads: 39
Keywords: 


Abstract:

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 $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}$.



Changes to previous version:

fixed abstract


Revision #1 to TR20-106 | 15th July 2020 19:32

Explicit Extremal Designs and Applications to Extractors





Revision #1
Authors: Eshan Chattopadhyay, Jesse Goodman
Accepted on: 15th July 2020 19:32
Downloads: 43
Keywords: 


Abstract:

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 $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}$.



Changes to previous version:

fixed abstract


Paper:

TR20-106 | 15th July 2020 18:06

Explicit Extremal Designs and Applications to Extractors





TR20-106
Authors: Eshan Chattopadhyay, Jesse Goodman
Publication: 15th July 2020 19:25
Downloads: 49
Keywords: 


Abstract:

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 $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}$.



ISSN 1433-8092 | Imprint