|
Instructor
Venue and time
- Monday, 10:30-13: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: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.
|