DIMACS - Graduate Student Combinatorics Seminar

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


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.

See: http://www.math.rutgers.edu/~ajr224/GCS.html