*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: The Big Data Theory and Randomized Algorithms
Abstract:
Advances in machine learning and developments in modern massive parallel computational systems motivate a large number of challenging questions for the theory of computing. How to make sense of massive amounts of noisy data? How to cluster billions of points and compare large images? How to design scalable algorithms for distributed systems?
I will present examples of settings in which these questions can be addressed through the design of randomized algorithms:
Through these examples I will illustrate how information-theoretic measures of performance such as query complexity and the number of rounds of communication play a key role in the design and analysis of such algorithms. I will show that even in the worst-case these fundamental problems can be solved almost optimally with respect to these measures. The information-theoretic nature is crucial here since lower bounds can be proved unconditionally, i.e. with no computational hardness assumptions.
This talk will be primarily based on two papers which will appear in STOC’14 (joint work with Andoni, Berman, Nikolov, Onak and Raskhodnikova) as well as other work by the speaker.
