Property Testing and Communication Complexity

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.