Communication Complexity (for Algorithm Designers)
by Tim Roughgarden
Publisher: Stanford University 2015
Number of pages: 150
Description:
Communication complexity offers a clean theory that is extremely useful for proving lower bounds for lots of different fundamental problems. The two biggest goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds; 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds.
Download or read it online for free here:
Download link
(2.8MB, PDF)
Download mirrors:
Mirror 1
Similar books
Introduction to Complexity Theoryby Oded Goldreich
Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.
(10739 views)
Think Complexity: Complexity Science and Computational Modelingby Allen B. Downey - Green Tea Press
This book is about complexity science, data structures and algorithms, intermediate programming in Python, and the philosophy of science. The book focuses on discrete models, which include graphs, cellular automata, and agent-based models.
(9314 views)
From Complexity to Creativityby Ben Goertzel - Plenum Press
This text applies the concepts of complexity science to provide an explanation of all aspects of human creativity. The book describes the model that integrates ideas from computer science, mathematics, neurobiology, philosophy, and psychology.
(15533 views)
Foundations of Cryptographyby Oded Goldreich - Cambridge University Press
The book gives the mathematical underpinnings for cryptography; this includes one-way functions, pseudorandom generators, and zero-knowledge proofs. Throughout, definitions are complete and detailed; proofs are rigorous and given in full.
(16786 views)