COM SCI 285CC: Communication Complexity
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.
4 units, lecture
Loading...
| ALEXANDER SHERSTOV | Fall 2025 | 10 | 90.0% (9) |
|---|
A-range % and grade counts cover only each instructor’s latest recorded term, shown in the "Latest Data From" column, combining all sections for the course. A-range % is the share of recorded letter grades (A+ through F) that are A+, A, or A−. Parentheses show the A-range count over the total letter-grade count. P/NP and incompletes are excluded. Records may be incomplete.
- Available Academic Terms
- Fall 2022 · Fall 2023 · Fall 2025