A Gentle Introduction to Communication Complexity
Stefan Mengel25 avr. 2019 - 14:00
Communication complexity is a classical subarea of theoretical computer science that is however not very well known in other parts of computer science. It studies basic questions on the communication costs when solving computational problems. There are many applications, e.g. in chip design, distributed algorithms and, more interestingly for AI researchers, in knowledge compilation.
Here I will give a very gentle introduction into some of the basic concepts of communication complexity. We will consider relatively simple models and study different techniques for lower bounds. We will also see how to use these models to prove lower bounds for OBDD representations of Boolean functions. If time allows, we also have a look at some more complicated models and show how they relate to more general representations in knowledge compilation.
This presentation will not be on cutting edge research in the area. Instead, it will be a tutorial on some basic aspects whose goal it is to introduce the members of CRIL to the very pretty area of communication complexity.