Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userImproved Extractors for Small-Space Sources
150
0
0.0
(
0
)
Added by
Jesse Goodman
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the problem of extracting random bits from weak sources that are sampled by algorithms with limited memory. This model of small-space sources was introduced by Kamp, Rao, Vadhan and Zuckerman (STOC06), and falls into a line of research initiated by Trevisan and Vadhan (FOCS00) on extracting randomness from weak sources that are sampled by computationally bounded algorithms. Our main results are the following. 1. We obtain near-optimal extractors for small-space sources in the polynomial error regime. For space $s$ sources over $n$ bits, our extractors require just $kgeq scdot$polylog$(n)$ entropy. This is an exponential improvement over the previous best result, which required $kgeq s^{1.1}cdot2^{log^{0.51} n}$ (Chattopadhyay and Li, STOC16). 2. We obtain improved extractors for small-space sources in the negligible error regime. For space $s$ sources over $n$ bits, our extractors require entropy $kgeq n^{1/2+delta}cdot s^{1/2-delta}$, whereas the previous best result required $kgeq n^{2/3+delta}cdot s^{1/3-delta}$ (Chattopadhyay, Goodman, Goyal and Li, STOC20). To obtain our first result, the key ingredient is a new reduction from small-space sources to affine sources, allowing us to simply apply a good affine extractor. To obtain our second result, we must develop some new machinery, since we do not have low-error affine extractors that work for low entropy. Our main tool is a significantly improved extractor for adversarial sources, which is built via a simple framework that makes novel use of a certain kind of leakage-resilient extractors (known as cylinder intersection extractors), by combining them with a general type of extremal designs. Our key ingredient is the first derandomization of these designs, which we obtain using new connections to coding theory and additive combinatorics.
rate research
Read More
The notion of semi-random sources, also known as Santha-Vazirani (SV) sources, stands for a sequence of n bits, where the dependence of the ith bit on the previous i-1 bits is limited for every $iin[n]$. If the dependence of the ith bit on the remaining n-1 bits is limited, then this is a strong SV-source. Even the strong SV-sources are known not to admit (universal) deterministic extractors, but they have seeded extractors, as their min-entropy is $Omega(n)$. It is intuitively obvious that strong SV-sources are more than just high-min-entropy sources, and this work explores the intuition. Deterministic condensers are known not to exist for general high-min-entropy sources, and we construct for any constants $epsilon, delta in (0,1)$ a deterministic condenser that maps n bits coming from a strong SV-source with bias at most $delta$ to $Omega(n)$ bits of min-entropy rate at least $1-epsilon$. In conclusion we observe that deterministic condensers are closely related to very strong extractors - a proposed strengthening of the notion of strong (seeded) extractors: in particular, our constructions can be viewed as very strong extractors for the family of strong Santha-Vazirani distributions. The notion of very strong extractors requires that the output remains unpredictable even to someone who knows not only the seed value (as in the case of strong extractors), but also the extractors outputs corresponding to the same input value with each of the preceding seed values (say, under the lexicographic ordering). Very strong extractors closely resemble the original notion of SV-sources, except that the bits must satisfy the unpredictability requirement only on average.
A rainbow $q$-coloring of a $k$-uniform hypergraph is a $q$-coloring of the vertex set such that every hyperedge contains all $q$ colors. We prove that given a rainbow $(k - 2lfloor sqrt{k}rfloor)$-colorable $k$-uniform hypergraph, it is NP-hard to find a normal $2$-coloring. Previously, this was only known for rainbow $lfloor k/2 rfloor$-colorable hypergraphs (Guruswami and Lee, SODA 2015). We also study a generalization which we call rainbow $(q, p)$-coloring, defined as a coloring using $q$ colors such that every hyperedge contains at least $p$ colors. We prove that given a rainbow $(k - lfloor sqrt{kc} rfloor, k- lfloor3sqrt{kc} rfloor)$-colorable $k$ uniform hypergraph, it is NP-hard to find a normal $c$-coloring for any $c = o(k)$. The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J. Comb. Theory. 1990) using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.
We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.
In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. In our first result, we show that any algorithm that distinguishes between uniform distribution on ${0,1}^n$ and uniform distribution on an $n/2$-dimensional linear subspace of ${0,1}^n$ with non-negligible advantage needs $2^{Omega(n)}$ samples or $Omega(n^2)$ memory. Our second result applies to distinguishing outputs of Goldreichs local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreichs pseudorandom generator $G$ fixes a predicate $P:{0,1}^k rightarrow {0,1}$ and a collection of subsets $S_1, S_2, ldots, S_m subseteq [n]$ of size $k$. For any seed $x in {0,1}^n$, it outputs $P(x_{S_1}), P(x_{S_2}), ldots, P(x_{S_m})$ where $x_{S_i}$ is the projection of $x$ to the coordinates in $S_i$. We prove that whenever $P$ is $t$-resilient (all non-zero Fourier coefficients of $(-1)^P$ are of degree $t$ or higher), then no algorithm, with $<n^epsilon$ memory, can distinguish the output of $G$ from the uniform distribution on ${0,1}^m$ with a large inverse polynomial advantage, for stretch $m le left(frac{n}{t}right)^{frac{(1-epsilon)}{36}cdot t}$ (barring some restrictions on $k$). The lower bound holds in the streaming model where at each time step $i$, $S_isubseteq [n]$ is a randomly chosen (ordered) subset of size $k$ and the distinguisher sees either $P(x_{S_i})$ or a uniformly random bit along with $S_i$. Our proof builds on the recently developed machinery for proving time-space trade-offs (Raz 2016 and follow-ups) for search/learning problems.
We give a deterministic, nearly logarithmic-space algorithm that given an undirected graph $G$, a positive integer $r$, and a set $S$ of vertices, approximates the conductance of $S$ in the $r$-step random walk on $G$ to within a factor of $1+epsilon$, where $epsilon>0$ is an arbitrarily small constant. More generally, our algorithm computes an $epsilon$-spectral approximation to the normalized Laplacian of the $r$-step walk. Our algorithm combines the derandomized square graph operation (Rozenman and Vadhan, 2005), which we recently used for solving Laplacian systems in nearly logarithmic space (Murtagh, Reingold, Sidford, and Vadhan, 2017), with ideas from (Cheng, Cheng, Liu, Peng, and Teng, 2015), which gave an algorithm that is time-efficient (while ours is space-efficient) and randomized (while ours is deterministic) for the case of even $r$ (while ours works for all $r$). Along the way, we provide some new results that generalize technical machinery and yield improvements over previous work. First, we obtain a nearly linear-time randomized algorithm for computing a spectral approximation to the normalized Laplacian for odd $r$. Second, we define and analyze a generalization of the derandomized square for irregular graphs and for sparsifying the product of two distinct graphs. As part of this generalization, we also give a strongly explicit construction of expander graphs of every size.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
