Algorithmic Aspects of Communication (Winter 2010)

Instructor: François Le Gall
Place: Thursday, 10:15 - 11:45, Room 102 of Science Building Number 7

Course outline

This course will address several algorithmic and complexity-theoretic aspects of communication systems. It will cover the basics of communication complexity theory, protocols for secure multiparty computation and related cryptographic tasks, and also recent topics such as network coding theory. This course will be taught in English.

Lectures

Lecture 1 [October 21]
Guidance and introduction: quick overview of communication complexity (the average and the median functions), secure computation (the millionaire's problem and secret sharing) and network coding (the butterfly network).

Lecture 2 [October 28]
Communication Complexity I: model of 2-party communication complexity, rectangles and partitions (Sections 1.1 and 1.2 of the Kushilevitz-Nisan textbook).

Lecture 3 [November 4]
Communication Complexity II: more about rectangles and partitions, the fooling set method, the rank method, the rectangle bound method (Sections 1.3, 1.4 and Chapter 2 of the Kushilevitz-Nisan textbook).

Lecture 4 [November 11]
Communication Complexity III: three examples (the Greater Than function, the Disjointness function, the Inner Product function), application to time-space tradeoffs for Turing machines, a randomized protocol for the Equality function (Section 1.3, Section 12.1, Section 3.1 of the Kushilevitz-Nisan textbook).

Lecture 5 [November 18]
Communication Complexity IV: definition of private coins and public coins randomized protocols, Newman's theorem, applications to space lower bounds for data stream algorithms (Section 3.1 and Section 3.3 of the Kushilevitz-Nisan textbook; "The space complexity of approximating the frequency moments" by Alon, Matias and Szegedy).

Lecture 6 [November 25]
Communication Complexity V: distributional complexity, lower bounds techniques for randomized communication complexity, discrepancy (Sections 3.4 and 3.5 of the Kushilevitz-Nisan textbook).

Lecture 7 [December 2]
Secure Computation I: secret sharing schemes, Shamir's construction ( "How to share a secret" by Shamir).

Lecture 8 [December 9]
Secure Computation II: Feldman's verifiable secret sharing scheme, main theorems on the existence of secure function evaluation protocols (Yao'82,BGW'88,RB'89,GMW'91), trapdoor one-way functions and oblivious transfer.

Lecture 9 [December 16]
Secure Computation III: construction of oblivious transfer from trapdoor one-way functions, description of a protocol that securely computes any function in the honest 2-party model (Section 7.3 of the Goldreich textbook).

Note: no class on December 23 and January 6 (Winter vacation).
Announcement: class on January 13 is cancelled.

Lecture 10 [January 20 -- last lecture]
Network coding: flow networks, the min-cut=max-flow theorem, examples of network coding protocols, the main theorem of multicast network coding (Chapters 1 and 2 of the Fragouli-Soljanin textbook).

Textbook and suggested reading

There is no required textbook for this course, but students who want to study in more depth the first topic of this course (Lectures 2-6) may refer to Communication Complexity by Kushilevitz and Nisan (Cambridge University Press, 1997). A very complete reference for secure computation is Chapter 7 of the two-volume book Foundations of Cryptography by Goldreich (Cambridge University Press, 2001 and 2004). A good reference for network coding (Lecture 10) is the book Network Coding Fundamentals by Fragouli and Soljanin (Now publishers, 2007), available online here.

Evaluation

Evaluation on submitted final reports.