• 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)).