CSIE 5118: Introduction to Communication Complexity



Venue and time

  • Monday, 10:30-13:00, room CSIE 544.


  • For correspondence, use my CSIE email: tonytan@csie.ntu.edu.tw
  • Please check this website regularly. Course notes and homework will be posted here.
  • All the announcements will also be posted here, as well as in the bulletin of this course in CEIBA.
  • Each homework weighs 25%.

Teaching assistants

  • Liu Han Sheng (b04902012@ntu.edu.tw), office hour: 13:00-14:00, room 401.
  • If needed, you may try to arrange another time slot with the TA directly.

Recommended textbooks

  • Communication complexity by E. Kushilevitz and N. Nissan.

Syllabus (tentative)

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

Notes on homework submission

  • You should write down your class number, your student number and your name in your homework solution.
  • Homeworks will be posted here on Mondays in the indicated week.
  • Their due dates are also always on Mondays before the class starts in the indicated week.
  • You can submit your homework earlier than the due date by slipping it under the door of my office.
  • Homework solution has to be handwritten or typewritten in a format that will be determined later.
  • 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.