Grading: 60% homework + 40% project
Final Project: due April 28th
Randomness is an extremely useful tool in almost all areas of computer science (such as algorithms, cryptography, and distributed computing) and mathematics. Can we derandomize algorithms, that is efficiently turn randomized algorithms into deterministic algorithms? Can we save random bits for tasks that do require randomness? Can we get randomness from imperfect sources of randomness that have little entropy? Can we construct mathematical objects such as graphs that share many useful properties to that of a random object? What does it mean for a combinatorial object such as a graph or a set of integers or a Boolean function to be “random-like”? In this course we will discuss answers to several questions of this nature, and along the way discuss constructions of very useful pseudorandom objects such as pseudorandom generators, expander graphs, randomness extractors, and Ramsey graphs.