dibs

COM SCI 285CC: Communication Complexity

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.

4 units, graduate

Offered Fall quarters

Predicted GPA
3.79
A or A minus
95%
D, F or withdrew
0%
Sections
No sections listed for this term. Offered Fall quarters.
By instructor
Fall 2022 to Fall 2025
All instructors
3.79 GPA
95% A
0% DFW
39 grades
SHERSTOV
3.87 GPA
95% A
0% DFW
39 grades
Prerequisites
Not read yet
Restrictions
Not read yet
Grading
Not read yet