Special Topics in Complexity Theory, Lecture 15
Thoughts 2018-03-12
Summary:
Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola 1 Lecture 15, Scribe: Chin Ho Lee In this lecture fragment we discuss multiparty communication complexity, especially the problem of separating deterministic and randomized communication, which we connect to a problem in combinatorics. 2 Number-on-forehead communication complexity In number-on-forehead (NOH) communication complexity each party sees […]