## Algorithmic Aspects of Communication (Winter 2012)

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

## Lectures

**Lecture 1 [October 4]**

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 11]**

Communication complexity I: formal model of communication protocols and rectangles.

**Lecture 3 [October 18]**

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

**Lecture 4 [November 1]**

Communication complexity III: randomized communication complexity, applications to space lower bounds for data stream algorithms ( "The space complexity of approximating the frequency moments" by Alon, Matias and Szegedy).

**Lecture 5 [November 8]**

Secure Computation I: secret sharing schemes, Shamir's construction ( "How to share a secret" by Shamir), verifiable secret sharing schemes.

**Lecture 6 [November 15]**

Secure Computation II: private information retrieval.

**Lecture 7 [November 29]**

Secure Computation III: error-correcting codes, the Hadamard code, locally decodable codes.

**Lecture 8 [December 6]**

Guest lecture by Prof. Pandu Rangan.

**Lecture 9 [December 13]**

Secure Computation IV: locally decodable codes and applications to private information retrieval.

**Lecture 10 [December 20]**

Secure Computation V: general two party protocols (feasibility of secure computation, oblivious transfer, Yao's protocol).

**Lecture 11 [January 10]**

Network Coding I: definitions and examples, the main theorem of multicast network coding (additional material).

**Lecture 12 [January 17]**

Network Coding II: proof of the main theorem of multicast network coding, coding rate vs. routing rate.

**Lecture 13 [January 24]**

Network Coding III: average coding rate for multicast problems.

**Lecture 13 [January 31, final lecture]**

Network Coding IV: 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.