Questions tagged [extractors]
The extractors tag has no usage guidance.
11
questions
1
vote
0
answers
56
views
Constructing lossless conductors using zigzag product - a doubt
Reference - this survey: https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
I am reading the section on constructing lossless conductors using a bipartite variant of zigzag product (section 10,...
- 91
4
votes
1
answer
175
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
2
votes
1
answer
196
views
Motivation for randomness extractors
I'm a maths masters student exploring how results in the geometry of finite fields, such as the finite field Kakeya conjecture, applies to randomness extractors. I'm not a computer scientist, and must ...
- 23
1
vote
0
answers
113
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, ...
- 161
5
votes
0
answers
154
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
1
vote
1
answer
136
views
deterministic randomness extractor and privacy
Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over the channel $P_{Y|X}$ which outputs $Y$ taking ...
- 425
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})...
user6973
3
votes
0
answers
77
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 $\...
user6973
19
votes
3
answers
692
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.6k
9
votes
0
answers
180
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)-...
- 651
23
votes
3
answers
887
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 ...
- 11k