Fall 2017 Course Descriptions
COMP 150-08 The Discrepancy Method
The Discrepancy Method is one of the most exciting and beautiful recent developments in mathematics and theoretical computer science. Closely related to the probabilistic method and derandomization, it touches areas as diverse as machine learning, number theory, computational geometry, circuit complexity, and linear programming. The probabilistic method was developed by Paul Erdos to demonstrate the existence of certain objects by showing that they have a positive probability of existence, and derandomization attempts to make this practical by converting the probability calculation into a construction algorithm.
We will be using Bernard Chazelle's "The Discrepancy Method", available at his web site at Princeton. We hope to bring together computer science and mathematics students through readings, discussions, and student papers or presentations.
Prerequisite: The ideal participant should have done well in COMP 160 or be a mathematics senior or graduate student.