** **
CPSC 461b Problem Set 1
[Course home page] [Course handouts]
YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPSC 461b: Foundations of Cryptography
 
Professor M. J. Fischer
Handout #3
February 9, 2004
Problem Set 1
Due in class on Tuesday, February 17, 2004.

Problem 1:   BPP bounds

[Textbook, Chapter 1, Exercise 4.]

Problem 2:   One-way functions imply P ≠ NP

[Textbook, Chapter 2, Exercise 2.]

Problem 3:   N-way selection using unbiased coins tosses

Define the bias of a distribution X on an N-element set S to be
ε =
max
x ∈ S 
Pr
[ X = x ] −  1
N

 .
That is, the bias is the maximum deviation of the algorithm's output distribution from the uniform distribution on S.
  1. Let Ut be a uniformly distributed random variable over a t-element set T. Show that for any function f: T → S, the distribution f(Ut) has bias at least 1/(2t) on S unless t is a multiple of N.

  2. Show that there exists a function g: T → S such that g(Ut) has bias at most 1/t.

  3. Let A(N) be a probabilistic polynomial time algorithm that, given an integer N (represented in binary), outputs a number in {1, …,N}. Assume N is not a power of two. Give a lower bound on the bias of the output distribution A(N) on {1,…,N}.



File translated from TEX by TTH, version 3.40.
On 9 Feb 2004, 22:01.