## 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.