CSIE 5118: Introduction to communication complexity

       

Instructor

  • Name: Tony Tan
  • Room: CSIE 516
  • Office hour: By appointment via email
  • Email: tonytan@csie.ntu.edu.tw
  • Personal website

Venue and time

  • Time: Monday, 09:30-11:15 (lecture) and 11:25-12:10 (tutorial)
  • Room: CSIE 546

Administration

  • Notes and homework will be posted in this website regularly.
  • This document (2016b-comm-admin.pdf) contains more information about the course.
  • To contact me, use: tonytan@csie.ntu.edu.tw

Schedule (tentative)

Week Dates Lesson Remark
I 20 Feb. Lesson 1. Preliminaries --
II 27 Feb. No lesson due to peace memorial holiday. --
III 6 Mar. Lesson 2. Deterministic protocols --
IV 13 Mar. Lesson 3. Fooling sets --
V 20 Mar. Lesson 4. Rank lower bounds --
VI 27 Mar. Lesson 5. Nondeterministic protocols HW 1 out.
VII 3 Apr. No lesson due to tomb sweeping holiday. --
VIII 10 Apr. Lesson 6. Det. and nondet. procotocols HW 1 due.
IX 17 Apr. Lesson 7. Ranks and covers --
X 24 Apr. Lesson 8. Randomized protocols HW 2 out.
XI 1 May -- --
XII 8 May Lesson 9. Det. and randomized protocols HW 2 due.
XIII 15 May Lesson 10. Distributional complexity and discrepancy --
XIV 22 May Lesson 11. Asymmetry communication and variable partition models HW 3 out.
XV 29 May No lesson due to dragon boat festival. --
XVI 5 Jun. Lesson 12 & 13. Applications on networks, VLSI and data structures HW 3 due.
XVII 12 Jun. Lesson 14. Applications on Turing machines HW 4 out.
XVIII 19 Jun. -- HW 4 due on 26 June 2017.

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.