Skip to main content
MathOverflow

Return to Question

correct spelling
Source Link
coudy
coudy
  • 18.7k
  • 5
  • 75
  • 135

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 Schwartz-Schwarz, and Jensen's inequality failed as well. Thank you

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 Schwartz, and Jensen's inequality failed as well. Thank you

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

texified.
Source Link
Federico Poloni
Federico Poloni
  • 20.2k
  • 2
  • 82
  • 120

Hey guys. I'mI'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

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

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

Hey guys. 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}^nX{0,1}^n->{0,1} such that given two inputs which are uniformly distributed over a large domain, output a bit which is close to uniform. Mathematically: for two sets A,B in {0,1}^n such that |A||B|>= (2^n)/(epsilon^2) the following holds: E(-1)^(f(x,y))<=epsilon, when E is the expectation when x,y get values at A,B respectively. I am required to show that f(x,y)=<x,y> is a uniformal bit generator. Nothing I have done worked, Cauchy Schwartz, and Jensen's inequality failed as well. Thank you

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 Schwartz, and Jensen's inequality failed as well. Thank you

Source Link
John
John
  • 21
  • 1

uniform bit generator

Hey guys. 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}^nX{0,1}^n->{0,1} such that given two inputs which are uniformly distributed over a large domain, output a bit which is close to uniform. Mathematically: for two sets A,B in {0,1}^n such that |A||B|>= (2^n)/(epsilon^2) the following holds: E(-1)^(f(x,y))<=epsilon, when E is the expectation when x,y get values at A,B respectively. I am required to show that f(x,y)=<x,y> is a uniformal bit generator. Nothing I have done worked, Cauchy Schwartz, and Jensen's inequality failed as well. Thank you