Dept Banner
Dept Banner

Calendar

Download as iCal file

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 -

Cole Franks, Rutgers University

"A theorem used in communication complexity and a conjectured generalization"

Time: 12:10 PM

Location: Hill Grad Student Lounge

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530