- Property Testing and Commun...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in September 2013
Property Testing and Communication Complexity
Speaker:
Grigory Yaroslavtsev
, Brown University
Date: Wednesday, September 11, 2013
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-G575
Event Type:
Room Description:
Host: Ilya Razenshteyn, MIT
Contact: Joanne Talbot Hanley, 3-6054, joanne@csail.mit.edu
Speaker URL: None
Speaker Photo:
None
Reminders to:
theory-seminars@csail.mit.edu, seminars@csail.mit.edu
Reminder Subject:
TALK: Algorithms & Complexity Seminar: Grigory Yaroslavtsev
Abstract:
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.
Research Areas:
Impact Areas:
Created by Joanne Talbot Hanley 
at Monday, September 09, 2013 at 10:57 AM.