- Recall Chernoff bounds!
- Make sure you can solve the following easier problem first:
you are given an algorithm A which takes as input
x and computes f(x) correctly with
probably 3/4. A's runtime is T(|x|).
Construct an algorithm B which takes as input
x and beta, and computes f(x)
correctly with probability probably 1-beta.
B's runtime should be O(T(|x| log(1/beta)).