Pseudorandom generators (PRGs) are key to understanding such questions. A pseudorandom generator maps a short, random string to a long ``pseudorandom" string that appears random to a large class of tests. PRGs are fundamental to cryptography, but such cryptographic PRGs rely on unproven assumptions. Instead, our focus will be on unconditional pseudorandom generators, meaning they don't require unproven assumptions, but are therefore weaker than cryptographic PRGs.

• Discrete Probability, including moments and deviation bounds of Markov, Chebyshev, and Chernoff;
• Algebra, including vector spaces, eigenvectors/eigenvalues, and finite fields;
• Complexity Theory, including P, NP, NP-completeness, and reductions;
• Other: basic combinatorics and graph theory; exposure to some randomized algorithms.

Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around or emailed. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web.