<p>Lecture, four hours; outside study, eight hours. Limited to graduate students. Mathematical maturity strongly encouraged. Introduction to communication complexity with coverage of fundamentals, key classic theorems, and current research directions. Consider function f whose arguments are distributed among several parties, making it impossible for any one party to compute f in isolation. Communication complexity theory studies how many bits of communication are needed to evaluate f. Pioneered in 1979 by Turing award winner Andrew Yao, communication complexity has become central area of theoretical computer science with deep open questions, beautiful mathematics, and vast array of applications. Letter grading.</p>

Computer Science

Known as the birthplace of the Internet and where countless other cutting-edge technologies took their first steps, the school is consistently ranked among the top 10 public engineering schools in the U.S.

Henry Samueli School of Engineering and Applied Science

Computer science is concerned with the design, modeling, analysis, and applications of computer systems.

General Catalog

Communication Complexity

COM SCI 285CC

4 units