Representations, Algorithms, and Computation on Groups

(Advanced Algorithms)

Fall 2012


ITCS @ IIIS, Tsinghua University
 
Instructor: Periklis A. Papakonstantinou [ppapakons.tsinghua.old@gmail.com]
Teaching assistants: Bangsheng Tang, Hao Song
Lectures: Monday 1.30-4.05pm (3x45min)
Office hours: Monday 12.30-1.20pm (or by appointment), FIT 4-608-7



News

[Dec 27] Assignment 4 is out.


Handouts, problem-sets, and links

References



Lectures

Date Topic
Dec 24 Sampling from the Symmetric Group: Dixon's result, Babai-Nikolov-Pyber, and other sampling and RW on symmertic group Cayley graphs.
Dec 17 The state of the art in Group Isomorphism algorithms -- lecture given by Bangsheng Tang
Standard algorithms, Abelian Groups, Abelian semidirect product with cyclic, and some remarks on other group classes
Dec 10 The state of the art in Group Isomorphism algorithms -- lecture given by Bangsheng Tang
Standard algorithms, Abelian Groups, Abelian semidirect product with cyclic, and some remarks on other group classes
Dec 3 Constructing expander graphs in small space, the zig-zag product, and Reingold's algorithm
Nov 26 Margulis construction: the full proof and some remarks on applications of harmonic analysis to computer science
Nov 19 Introduction to graph expanders and some algorithmic applications
Nov 12 The full proof of the Alon-Roichman Theorem -- and some consequences
Nov 5 Alon-Roichman Theorem: measure concetration on linear operators and proof outline
Oct 29 More on expanders, and relations to other pseudo-random objects.
Explicit constructions and the zig-zag product. Undirected connectivity in small space.
Oct 22 Expander graphs, notions of expansion, mixing phenomena.
Oct 15 Introduction to Expander Graphs and Random Walks.
Undirected connectivity in randomized small space
Oct 8 A crash course on representation theory (part 2)
Sep 24 A crash course on representation theory (part 1)
A crash course on finite groups (part 3)
Sep 17 A crash course on finite groups (part 2)
Sep 10 Introduction, class overview
A crash course on finite groups (part 1)


Last Modified: December 30, 2012