CSIE 5118: Introduction to Communication Complexity
Venue and time
- Monday, 10:30-13:00, room CSIE 544.
- For correspondence, use my CSIE email: firstname.lastname@example.org
- 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%.
- Liu Han Sheng (email@example.com), office hour: 13:00-14:00, room 401.
- If needed, you may try to arrange another time slot with the TA directly.
- Communication complexity by E. Kushilevitz and N. Nissan.
||Lesson 1. Preliminaries
||Lesson 2. Deterministic protocols
||Lesson 3. Fooling sets
||HW 1 out.
||Lesson 4. Rank lower bounds
||Lesson 5. Non-deterministic protocols
||Lesson 6. Communication complexity and covers
||HW 1 due. HW 2 out.
||Lesson 7. More on covers
||Lesson 8. Randomized protocols
||Lesson 9. Continuing lesson 8
||HW 2 due.
||Lesson 10. Distributional complexity
||HW 3 out.
||Lesson 11. Linear lower bound for disjoint function
||Lesson 12. Continuing lesson 11
||HW 3 due.
||Lesson 13. Some applications
||HW 4 out.
||Lesson 14. Some applications
||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.