Title: A Theorem Used in Communication Complexity and a Conjectured Generalization
Speaker: Cole Franks, Rutgers University
Date: Wednesday, September 28, 2016 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Unbounded error probabilistic communication complexity of a bivariate function is the number of bits two players, one having the first input and the other the second, would need to share for one of them to have a strictly better than 1/2 chance at guessing the value of the function. This problem has some nice equivalent formulations, and some good lower and upper bounds. A theorem involved in the lower bound, now called Forster's theorem, has popped up in some other places and has several nice proofs. We'll talk about the model, the theorem, and a possible generalization of said theorem.