ﻻ يوجد ملخص باللغة العربية
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.
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 remain
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
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 distin
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