# Questions tagged [extractors]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
862 views

### From Extractors to Pseudorandom Generators?

Luca Trevisan showed how many constructions of pseudorandom generators can in fact be thought of as extractor constructions: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Is there a ...
• 10.9k
683 views

### Running a BPP algorithm with a half-random, half-adversarial string

Consider the following model: an n-bit string r=r1...rn is chosen uniformly at random. Next, each index i∈{1,...,n} is put into a set A with independent probability 1/2. Finally, an adversary ...
• 13.5k
179 views

Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-... • 651 5 votes 0 answers 150 views ### Applications of small Kakeya sets over finite fields It was proved by Dvir that a Kakeya set in$\mathbb{F}_q^n$has size at least$q^n/n!$, a bound which was later improved to$q^n/2^n$. For$n = 2$and$q$odd the exact bound is$q(q+1)/2 + (q-1)/2$... • 190 4 votes 1 answer 158 views ### Strong seeded randomness extractors with low entropy loss I would like to implement a strong seeded randomness extractor for flat sources as a part of my project. Most of the literature on seeded extractors is concentrated on minimizing seed length. ... • 141 4 votes 0 answers 147 views ### Strong extractors with reusable seeds I have convinced myself of the following: For every$(k,\epsilon^2\hspace{.005 in})$-strong extractor Ext, for every distribution$X$, if$\;\; k\leq\:H_{\infty}(\hspace{.01 in}X\hspace{.015 in})... 