The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
0answers
88 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
69 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
506 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
148 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 ...
20
votes
3answers
573 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 ...