Abstract:
In this talk we will discuss multiparty communication complexity in the message-passing model, where we have k machines, each having a piece of data and they want to jointly compute some function defined on the union of the k data sets via communication. The communication is point-to-point, and the goal is to minimize the total communication between the k sites. This model captures all point-to-point distributed computational models for Big Data in terms of communication complexity, including the BSP model and the MapReduce model. Problems we consider in this model include statistical & graph problems, numerical linear algebra and database queries.

In this talk we will introduce new techniques developed in the last two years for proving communication lower bounds in the message-passing model. We believe that these techniques will have a wide applicability.

Biography:
Dr. Zhang is currently a postdoctoral fellow at IBM Research Almaden. He will join Indiana University Bloomington as a faculty member in August 2013. He obtained his Ph.D. degree in Computer Science and Engineering from HKUST in 2010, and his B.Sc. degree in Computer Science from Fudan University in 2006. He has also been a postdoctoral fellow at Center for Massive Data Algorithmics, Computer Science Department, Aarhus University.

His current research interests include algorithms for massive data; data streams; algorithms on distributed data; data structures; external memory algorithms; database algorithms; communication complexity.