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

Relevant URL:

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 ShannonÂ’s 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:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Joanne Talbot Hanley Email at Monday, September 09, 2013 at 10:57 AM.