The extractors tag has no wiki summary.
4
votes
0answers
80 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 ...
3
votes
0answers
66 views
Are there any “two-sided” strong blenders?
My question is related to explicit extractors and strong blenders. We can define explicit strong blender in a straight forward way.
I want to know if there are any known explicit strong blenders ...
18
votes
3answers
446 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 ...
9
votes
0answers
140 views
Pseudorandom object yielding shrinkage in $\ell_p$ norm?
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 ...
19
votes
3answers
543 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 ...
