Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> FEB 9: Theory CS Seminar
About
Undergraduate
Graduate
Research
People
News & Events
FEB 9: Theory CS Seminar
Event date: Tuesday, February 09, 2010, at 3:15 PM
Location: Pratt Building Rm. 266
Speaker: Joshua Brody
Dartmouth College
Title: Communication Complexity and You: A Winning Combination
Abstract: Communication Complexity has been used to prove lower bounds and hardness results in a wide variety of domains, from the theoretical (circuit complexity, proof complexity) to the practical (streaming algorithms, data structures, etc.)
In this talk I'll present some recent results on two communication problems: Gap Hamming Distance and Multiparty Pointer Jumping. The Gap Hamming Distance problem captures the hardness of computing certain functions on data streams, even when randomness and approximation are used. Proving sufficiently strong lower bounds for Multiparty Pointer Jumping would resolve a major open question in circuit complexity.
Despite the different nature of the applications, the lower-bounds proofs in each problem use similar techniques, which should be useful in other problems as well.
The results on Gap Hamming Distance are joint work with Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf. This talk assumes no prior knowledge of communication complexity.