2
$\begingroup$

I'm trying this question for days but no luck, if someone can give me a lead or an article that solves this.. it would be great:

A uniform bit generator is a function $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ such that given two inputs which are uniformly distributed over a large domain, outputs a bit which is close to uniform.

Mathematically: for two sets $A,B \subseteq \{0,1\}^n$ such that $|A||B|\geq (2^n)/(\varepsilon^2)$ the following holds: $E[(-1)^{f(x,y)}]\leq\varepsilon$, when $E$ is the expectation when $x,y$ get values at $A,B$ respectively. I am required to show that $f(x,y)=\langle x,y \rangle$ is a uniformal bit generator. Nothing I have done worked, Cauchy-Schwarz, and Jensen's inequality failed as well. Thank you

Improve this question
$\endgroup$
1
  • $\begingroup$ Please fix the math, so that it is LaTeX formatted. How about taking the parity of the number of ones in the inputs? $\endgroup$
    – Per Alexandersson
    Commented Mar 7, 2012 at 20:24

1 Answer 1

Reset to default
1
$\begingroup$

What you are looking for is special-case of a more general, and quite well-studied object in computer science, namely, a Randomness Extractor. The Wikipedia article linked to should get you started in the correct direction, in case you did not already know it.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .