Interested in big data, machine learning, theoretical computer science? Come hear Professor of Computer Science Amit Chakrabarti talk about his research in the theory of data streaming algorithms this evening! May 12, 5:30 PM - 6:30 PM Kemeny 108 PIZZA WILL BE SERVED. TITLE: Big Data, Communication Games, and an Inverse-Square Law ABSTRACT: It is now common knowledge that we live in an era of "Big Data". Science, engineering, technology, and even the routine activities of modern life are producing increasingly large data streams, at petabyte or exabyte scales. At these scales, what used to be routine algorithmic tasks for "small data"---such as estimating basic statistics of a population or understanding the connectivity structure of a graph---may now be challenging problems, with new theoretical principles needed to understand and solve them. Most of my work focuses on building such theoretical principles. One key result, that I shall highlight in this talk, is an inverse-square law that can be summarized as follows. The working memory required for the statistical and graph-theoretic estimation tasks mentioned above need only grow sub-linearly in the input size (enabling efficient processing of big data) but must grow as the inverse square of the estimation error (revealing a fundamental computational limit). Communication games---where two or more players collaborate to compute on a massively-long input distributed amongst them---play a crucial role in establishing such theoretical principles of big data analysis. I shall demonstrate this connection with several examples, and give a brief overview of the mathematics behind the above inverse-square law.