Probabilistic Methods in Computer Science

Description

In this research- and reading-oriented graduate course, we will study the probabilistic method and its numerous applications to problems in many different areas of computer science.

The idea behind the probabilistic method itself is deceptively simple: sometimes, the best way to show that some type of object exists is not to construct one explicitly, but instead to argue that a random construction gives this type of object with non-zero probability. We will see in the course how this idea has far-reaching consequences in:

• Complexity Theory. The probabilistic method gives a powerful tool in proving the existence of “hard” functions and establishing the ultimate limits of many different models of computation.

• Randomized Algorithms. The probability method itself often only aims to show that an object of a given type exists with non-zero probability. But in many situations, the proofs can be modified easily to show that various objects exist with large probability. This fact can often be used to design surprisingly simple and powerful randomized algorithms for various computational tasks.

• Deterministic Algorithms. The probability method is also a powerful tool in the design and analysis of deterministic algorithms. In some cases, this is done via derandomization techniques; in other cases, the probabilistic method is used directly in the proofs of correctness of deterministic algorithms.

In the course, we will aim to read one chapter of the textbook per week. The Monday lectures will be devoted to presenting and discussing the main theorems of the week’s chapter. During the Wednesday lectures, we will break out into smaller groups in a problem-solving session where we apply the probabilistic method to a variety of different problems from different areas of computer science.

The final component of the course is a research project, in which each participant in the class will pursue active research on a topic related to the course.