
Instructor
Venue and time
 Monday, 10:3013:00, room CSIE 544.
Administration
 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:0014: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. Nondeterministic 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.
