Algorithmic Aspects of Communication (Winter 2013)

Instructor: François Le Gall
Place: Thursday, 10:30 - 12:00, 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 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. Error-correcting codes: foundations and examples of efficient codes
4. Network coding: formulation and examples, the max-flow bounds

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.

Lectures

Lecture 1 [October 3]
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 10]
Communication complexity I: formal model of communication protocols and rectangles.

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

Lecture 4 [October 24]
Communication complexity III: randomized communication complexity.

Lecture 5 [October 31]
Communication complexity IV: applications to space lower bounds for data stream algorithms ( "The space complexity of approximating the frequency moments" by Alon, Matias and Szegedy).
Secure Computation I: definition of secret sharing schemes.

Lecture 6 [November 7]
Secure Computation II: secret sharing schemes, Shamir's construction ( "How to share a secret" by Shamir), verifiable secret sharing schemes.

Lecture 7 [November 14]
Secure Computation III: definition of private information retrieval (PIR), example of PIR with information-theoretic privacy and example of PIR with computational privacy.

Lecture 8 [November 21]
Secure Computation IV (PIR and Error-Correction Codes, Part 1): the coding problem, error correcting codes, Hadamard codes.

Lecture 9 [November 28]
Secure Computation V (PIR and Error-Correction Codes, Part 2): definition of locally decodable codes, local decodability of Hadamard codes, relation with PIR schemes.

Lecture 10 [December 5]
Secure Computation VI (PIR and Error-Correction Codes, Part 3): construction of locally decodable codes from locally correctable linear codes, local decodability of Reed-Muller codes, applications to PIR schemes.

Lecture 11 [December 12]
Secure Computation VII (general two-party secure computation, Part 1): definitions, examples, feasibility of secure computation.

Lecture 12 [December 19]
Secure Computation VIII (general two-party secure computation, Part 2): feasibility of secure computation, oblivious transfer, Yao's protocol.

Lecture 13 [January 9]
Network Coding I: definitions and examples, the main theorem of multicast network coding (additional material).

Lecture 14 [January 16]
Network Coding II: proof of the main theorem of network coding (continued), coding versus routing rate.

Lecture 15 [January 23]
Network Coding III: average coding rate for multicast problems, the k-pair problem.

Evaluation

Evaluation on submitted final reports. Here are the assignments.