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.