Algorithmic Aspects of Communication (Winter 2014)

Instructor: François Le Gall
Place: Thursday, 10:30 - 12:00, Room 102 of Science Building Number 7
Tentative schedule: 10/2, 10/9, 10/16, 10/23, 10/30, 11/6, (no lecture on 11/13), 11/20, 11/27, 12/4, 12/11, 12/18, 1/8, 1/15, 1/22

Course outline

This course will address several algorithmic and complexity-theoretic aspects of communication systems. It will cover the basics of communication complexity theory and error-correcting codes, 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.

Topics

1. Communication complexity: deterministic and randomized protocols, lower bounds techniques, applications
2. Secure computation: secret sharing schemes, secure function evaluation
3. Private Information Retrieval and error-correcting codes
4. Network coding: formulation and examples, the max-flow bounds

Lectures

Lecture 1 [October 2]
Guidance and introduction: quick overview of communication complexity (the equality function), secure computation (the millionaire's problem and secret sharing), error correction, and network coding.

Lecture 2 [October 9]
Communication complexity I: formal model of communication protocols and rectangles.

Lecture 3 [October 16]
Communication complexity II: lower bound techniques (the fooling set method, the rank method), applications to space-time tradeoffs for Turing machines.

Lecture 4 [October 23]
Communication complexity III: randomized communication complexity (definition, first application to data streams).

Lecture 5 [October 30]
Communication complexity IV: applications of randomized communication complexity to space lower bounds for data stream algorithms ("The space complexity of approximating the frequency moments" by Alon, Matias and Szegedy), public coins versus private coins.

Lecture 6 [November 6]
Secure Computation I: definition of threshold secret sharing schemes, Shamir's construction ("How to share a secret" by Shamir), general secret sharing schemes.

Lecture 7 [November 20]
Secure Computation II: verifiable secret sharing schemes, private information retrieval (definition, example of two-server information-theoretically private information retrieval protocol).

Lecture 8 [November 27]
Secure Computation III: private information retrieval (example of one-server computationally private information retrieval protocol).

Lecture 9 [December 4]
Secure Computation IV: general two-party protocols (definitions, Yao's protocol for the millionaires' problem).

Lecture 10 [December 11]
Secure Computation V: general two-party protocols (oblivious transfer, general theorems).
Network Coding I: flow networks.

Lecture 11 [December 18]
Network Coding II: definition of multicast network coding, the main theorem of network coding (1/2).

Lecture 12 [January 8]
Secure Computation III: the main theorem of network coding (2/2), coding rate versus routing rate.

Lecture 13 [January 15]
Network Coding IV: coding rate versus average coding rate.

Lecture 14 [January 22, last lecture]
Network Coding V: the k-pair problem.

Textbook and suggested reading

There is no required textbook for this course, but students who want to study in more depth communication complexity 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 is the book Network Coding Fundamentals by Fragouli and Soljanin (Now publishers, 2007), available online here.

Evaluation

Evaluation on submitted final reports.