These hints can give you a nudge if you are stuck on a problem. I recommend trying the problems without hints for at least a couple days before you look. If you're still stuck after looking at the hints, ask on Piazza.

Click to reveal hints.

Problem 1

• Hint 1

  You'll need to run the algorithm many times and aggregate the results somehow.
• Hint 2

  Outputting the mean doesn't work. Why not?

Problem 2

• Hint 1

  The Chernoff bound doesn't work as well when the multiplicative error is close to 1.
• Hint 2

  Try a different bound.

Problem 3

• Hint 1

  Try constructing the committees one at a time.
• Hint 2

  It's often easier to handle binomial distributions than other kinds of distributions. For example, if you pick set X by including every element independently with probability p, then what is the distribution of |X|? what is the distribution of |X intersect Y| for any other set Y?

Problem 4

• Hint 1

  Applying LLL directly seems to run into a problem.
• Hint 2

  How can you get rid of the problem?