MAT 576
Topics in Pseudorandomness

Spring 14

News:
· If you are taking this course or want to get announcements about upcoming lectures please join the mailing list (you need to do this even if you are a registered student).

Administrative

Lectures: Mon/Wed 1:30pm, room: Fine Hall 1001 (10th floor, Math building)

Professor: Zeev Dvir (follow link for contact information)
Office Hours: By appointment.


Course Description

The course will focus on explicit constructions of combinatorial/algebraic objects that have 'random-like' properties. Examples of such `pseudo-random' objects include expander graphs (sparse graphs which are highly connected), Ramsey graphs (graphs with no large clique/independent set), error correcting codes (subspaces without low weight vectors) and more. In all of these examples, a randomly chosen object will be good with high probability but constructing an explicit example is highly non trivial. The first part of the course will focus on expander graphs and recent generalizations of these to the setting of hyper-graphs (or simplicial complexes). We will survey the classical theory of expanders (Laplacians, Cheeger inequalities, etc..) and see what part of this theory can generalize to hyper-graphs.


Reading:

General reading on Expander graphs: Some papers on random walks Constructions of expanders Simplicial complexes