Communication Complexity

Communication complexity is the mathematical study of scenarios where several parties need to communicate to achieve a common goal. This tutorial text explains fundamentals and recent developments in an accessible and illustrated form, including applications in circuit complexity, proof complexity, streaming algorithms and distributed computing.

Complexitatea comunicarii este studiul matematic al scenariilor in care mai multe parti trebuie sa comunice pentru a atinge un obiectiv comun. Acest tutorial explica elementele fundamentale si evolutiile recente intr-o forma accesibila si ilustrata, inclusiv aplicatii in complexitatea circuitului, complexitatea probelor, algoritmii de streaming si calculul distribuit.