COMP 760 (Winter 2014): Introduction to communication and information complexity

Instructor's contact: See my homepage.
Time and Location: Monday-Wednesday 10:05-11:25 at McConnell 103.

What is it about? This course is intended for graduate students in theoretical computer science or mathematics. It is a topics course in communication complexity and information complexity. The setting is that there are two players (with unlimited computational power), and given a function f(x,y), they want to agree on a communication protocol for the following purpose: Each of the players receives an n bit input, say x and y. Neither knows the other's input, and they wish to use the protocol to collaboratively compute f(x,y). Communication complexity is concerned with minimizing the number of bits communicated by the players for the worst-case choice of inputs x and y. Information complexity is concerned with the amount of information that the communicated bits reveal about the inputs x and y to the other player or to the external observer. The areas of communication and information complexity are currently very active fields of research in theoretical computer science, and they employ a surprisingly vast range of techniques and tools from other areas of mathematics.

What are the prerequisites? The main prerequisite is mathematical maturity and familiarity with basic background in linear algebra, mathematics analysis, and probability theory.

Evaluation? It will be based on assignments and a final presentation.