Graduate Student Combinatorics Seminar Sponsored by DIMACS
A theorem used in communication complexity and a conjectured generalization
Location: Hill Grad Student Lounge
Date & time: Wednesday, 28 September 2016 at 12:10PM - 12:11PM
Cole Franks, Rutgers University: 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.