MATH 288: Analytic Methods in Computer Science

Note: If this course is being taught this semester, more information can be found at the course home page.

Cross Listed

CSC 288/488.

Prerequisites

Students are expected to have familiarity with undergraduate level discrete mathematics (such as Math 150), graph theory (such as Math 248 or CSC 282), linear algebra (such as Math 165 or 173), and probability (such as Math 201).

Description

(none)

Topics covered

The purpose of this course is two-fold. First is to give a brief introduction to a number of areas in theoretical computer science such as coding theory, PAC learning, clustering, approximation algorithms, randomized algorithms, Ramsey theory, program/property checking, social choice theory, probabilistically checkable proofs, derandomization. Second is to look at each mentioned area through an analytic lens; That is, we introduce tools in spectral graph theory and Fourier analysis of boolean functions and use them to resolve major problems in each of those areas.

(none)