Property Testing and Communication Complexity
, Brown University
Date: Wednesday, September 11, 2013
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Ilya Razenshteyn, MIT
Contact: Joanne Talbot Hanley, 3-6054, firstname.lastname@example.org
Speaker URL: None
TALK: Algorithms & Complexity Seminar: Grigory Yaroslavtsev
Property testing, pioneered by Blum, Goldreich, Goldwasser, Luby, Ron, Rubinfeld and Sudan, is the study of extremely fast randomized algorithms for approximate decision making.
Communication complexity is a mathematical theory introduced by Yao in 1979 to extend Shannons information theory to the two-party setting.
We will survey recent results on the boundary between communication complexity and property testing. Over the last two years this connection proved to be very fruitful for developing new upper and lower bounds in both areas, as well as extending both fields in new directions.
Created by Joanne Talbot Hanley at Monday, September 09, 2013 at 10:57 AM.