CSIE 5118: Introduction to communication complexity

       

Instructor

Venue and time

  • Friday, 10:30-13:00, room CSIE 546.

Administration

  • This document (2017b-comm-admin.pdf) contains more information about the course.
  • To contact me, use: tonytan@csie.ntu.edu.tw

Syllabus (tentative)

Part Week Dates Lesson Remark
A I 2 Mar. Lesson 1. Preliminaries --
B II 9 Mar. Lesson 2. Deterministic protocols --
III 16 Mar. Lesson 3. Fooling sets --
IV 23 Mar. Lesson 4. Rank lower bounds HW 1 out.
C V 30 Mar. Lesson 5. Non-deterministic protocols --
VI 6 Apr. -- --
VII 13 Apr. Lesson 6. Comm. complexity and covers HW 1 due.
VIII 20 Apr. Lesson 7. Continuing lesson 6 HW 2 out.
IX 27 Apr. -- --
D X 4 May Lesson 8. Randomized protocols --
XI 11 May -- --
XII 18 May Lesson 9. Continuing lesson 8 HW 2 due. HW 3 out.
E XIII 25 May Lesson 10. Distributional complexity --
XIV 1 Jun. Lesson 11. Discrepancy --
XV 8 Jun. Lesson 12. Linear lower bound for disjoint function HW 3 due.
XVI 15 Jun. Lesson 13. Continuing lesson 12 --
F XVII 22 Jun. Lesson 14. Some applications HW 4 out.
XVIII 29 Jun. -- HW 4 due.

Notes on homeworks

  • You should write down your class number, your student number and your name in your homework solution.
  • You can submit your homework earlier than the due date by slipping it under the door of my office.
  • Homework can be handwritten or typewritten. If it is handwritten, the writing must be legible.
  • The tidiness of your homework contributes to your grade.
  • Discussions/collaborations are allowed, but make sure that you acknowledge that you do your homeworks in collaboration and that you understand and write down your own solutions.
  • Points will be deducted if you don't understand your own solutions.