CSE
-
IITM
CS6850 - Communication Complexity (Self-Study)
Jan-May : 2015
Home
Information
Lectures
Activities
References
Today : Sat, Apr 20, 2024
No lecture
Announcements
Jan 20 : First Lecture Jan 20 TUE, 5-5:30 PM at CS32.
Back to Courses
Meetings
Click on the theme item for the meeting plan for that theme.
Click on the meeting item for references, exercises, and additional reading related to it.
Theme 1 :
- 8 meetings
Meeting 01 : Tue, Jan 20, 05:00 pm-05:35 pm -
Introductory Lecture.
References
Exercises
Reading
Introductory Lecture.
References
:
None
Meeting 02 : Thu, Jan 29, 04:00 pm-05:15 pm -
More on protocols. Combinatorial Rectangles. Fooling Sets. Large fooling set ==> high Communication Complexity.
References
Exercises
Reading
More on protocols. Combinatorial Rectangles. Fooling Sets. Large fooling set ==> high Communication Complexity.
References
:
None
Meeting 03 : Fri, Feb 06, 01:00 pm-02:00 pm -
Communication matrix. Rank. Protocol Covers. Non-determinism.
References
Exercises
Reading
Communication matrix. Rank. Protocol Covers. Non-determinism.
References
:
None
Meeting 04 : Fri, Feb 20, 06:00 am-06:00 am -
Non-determinism vs determinism.
References
Exercises
Reading
Non-determinism vs determinism.
References
:
None
Meeting 05 : Sat, Feb 21, 06:00 am-06:00 am -
Randomized COmmunication Complexity. Definitions. Relations to deterministic Complexity.
References
Exercises
Reading
Randomized COmmunication Complexity. Definitions. Relations to deterministic Complexity.
References
:
None
Meeting 06 : Fri, Feb 27, 06:00 am-06:00 am - Raghu and Shijin
Public vs Private coin protocols.
References
Exercises
Reading
Public vs Private coin protocols.
References
:
None
Meeting 07 : Mon, Mar 02, 06:00 am-06:00 am - Shijin+ Srini
Direct sum.
References
Exercises
Reading
Direct sum.
References
:
None
Meeting 08 : Fri, Mar 20, 06:00 am-06:00 am - Shijin + Srini
More on Direct sums: Nonderministic and Deterministic cases. Properties of Disjointness function.
References
Exercises
Reading
More on Direct sums: Nonderministic and Deterministic cases. Properties of Disjointness function.
References
:
None