Instructor: Shengyu Zhang

Lectures: 2:30pm-5:15pm, Monday, Sino Building UG06

TA: Liu, Yang. Email: yliu@cse.cuhk.edu.hk, Office: SHB606, Office time: 4pm - 6pm, Wednesday. 

Tutorials: 4:30pm - 5:30pm, Thursday. Venue: LSK (李兆基樓) 202

Topics: The course is about the ultimate efficiency that algorithms and communication protocols can achieve in various settings. We will see neatly designed algorithms with surprisingly low computation cost obtained by exploiting combinatorial and algebraic structures, and also study the limitation of various techniques and modes of computation.

The last offering of this course (in 2011) basically followed the textbook by Arora and Barak. This year it's gonna focus more on concrete models, and I plan to exhibit some clever algorithms/protocols besides lower bounds. There is no fixed textbook; the materials are from different books and papers. Detailed lecture notes, with pointers to further reading materials will be provided on the way.

Grading: Homework assignments (50%) + Final (50%)