The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
48 views

An algorithm for extracting grammars given existing grammar

Let all the grammars of concern here be CFGs. Let $A$ be a grammar with rules $A^i \Rightarrow a_1^i \dots a_{n_i}^i, \ i = 1 \dots n$, where each $a_i^j$ is either a terminal in $\Sigma$ or a rule ...
0
votes
0answers
51 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 ...
4
votes
0answers
91 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
515 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
155 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
580 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 ...