CSE 5339 - Randomness and geometry in the design of algorithms

Instructor: Luis Rademacher.
Lectures: WeFr 3:00PM-3:55PM, BO0313

Question: Does randomization help?

In this course we will get insight into one the greatest mysteries of computer science: Does randomization help? We will study the basic ingredients in the design and analysis of randomized algorithms, see some of the important examples and discuss select recent developments in randomized algorithms, with an aim towards understanding some contemporary research questions.
We will also discuss the use of non-obvious geometric ideas in the design of algorithms. For example, it is helpful in the analysis of (not necessarily geometric) data to imagine that this data lives in Euclidean space.
Topics will include the complexity of randomized algorithms, probabilistic tools and inequalities, and lower bound techniques. Among the examples, there will be applications to data analysis and machine learning.


Helpful courses/topics (NOT required):

The following topics are helpful but not required, as we may review some of them near the beginning of the course as needed: linear algebra, probability, a course about algorithms (such as 6331 (formerly 780)) and a course about the theory of computation (such as 6321 (formerly 725)).

Recommended readings:

Office hours:

By instructor, Dreese Labs 495, Tue 2:30-3:30pm or by appointment.

Problem Sets:

PS1 (due lecture on Mach 6th).


Depending on the number of students and interest, a combination of (some of, but not necessarily all of) homework, paper presentations and working on a research project (definitely no exams).

Topics (tentative):

Introduction to randomized algorithms, basic examples, MIN-CUT. Analysis.
Complexity of randomized algorithms: RP, coRP, BPP, ZPP.
Probabilistic tools. Concentration Inequalities. Markov, Tchebycheff, Chernoff. Examples. The coupon collector's problem.
Complexity of high dimensional geometric properties: center of mass, covariance, volume.
Complexity lower bounds. Game-theoretic techniques, Yao's min-max principle.
Introduction to the probabilistic method. Example: Shannon's theorem. Error correcting codes. Derandomization.
Expander Graphs.
Random projection. Randomized low rank matrix approximation. Principal component analysis, Independent component analysis, related tensor methods and applications to machine learning and data analysis.
Related topics in statistical learning: sample approximation, uniform convergence, Glivenko-Cantelli theorem, Vapnik-Chervonenkis theory, VC-dimension. Extensions.