Questions tagged [extractors]
The extractors tag has no usage guidance.
5
questions with no upvoted or accepted answers
9
votes
0answers
178 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 $\|\mathrm{Ext}(X,Y)-...
5
votes
0answers
140 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$ ...
4
votes
0answers
145 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})...
3
votes
0answers
75 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 $\...
1
vote
0answers
111 views
Extractor with somewhat corrupted seeds
In conditional min-entropy extractor, there is a joint distribution $(X,Y)$ such that if the average min-entropy (for some appropriate notion of it) ${\rm H}_\infty(X|Y)$ is large, then ${\rm Ext}(X, ...
