Sketching, Streaming and Sub-linear Space Algorithms

Piotr Indyk, MIT Abstract: Data stream algorithms are algorithms that perform computation over streams of data using only a limited amount of space. The field has experienced a significant growth over the last decade. Data stream algorithms have found applications in many domains, including analysis of massive data sets and network monitoring. At the same time, the field has been enriched by the discovery of strong connections to other areas, such as metric embeddings, communication complexity and compressed sensing. The tutorial will provide an introduction to streaming algorithms and related concepts. In the first part I will give an overview of the basic problems amenable to the streaming approach, and of the corresponding algorithmic techniques. In the second part I will focus on the specific problem of computing sparse approximations of a data stream, and describe old and new algorithms for this task. This tutorial is based on a graduate course under the same name, with notes available at http://stellar.mit.edu/S/course/6/fa07/6.895. True to the spirit of the material, I will attempt to compress one semester worth of material into 90 minutes. Bio: Piotr Indyk joined MIT in September 2000, after earning PhD from Stanford University. Earlier, he received Magister degree from Uniwersytet Warszawski in 1995. As of July 2007, he holds the title of Associate Professor with Tenure in the Department of Electrical Engineering and Computer Science. Piotr's research interests include: computational geometry (especially in high dimensional spaces), algorithms using sublinear time and/or space and streaming algorithms. He is also interested in algorithmic coding theory and pattern matching problems. Piotr is a recipient of NSF CAREER Award (2002), Sloan Fellowship (2003) and Packard Research Fellowship (2003).

Algorithmic Game Theory: Some recent results

Christos Papadimitriou, UC Berkeley Abstract: There are three major trends in the new field of Algorithmic Game Theory: computational mechanism design, the price of anarchy, and the computation of equilibria; this talk describes one recent result in each. We show computational complexity lower bounds on truthful and approximately efficient mechanisms; we revisit the Roughgarden-Tardos result on selfish routing when routing decisions are made by the nodes, not the flows; and we show that Nash equilibria can be approximated well in anonymous games, a very broad and useful class of games. Joint work with Costis Daskalakis, Michael Schapira, Yaron Singer, and Greg Valiant. Bio: Prof. Papadimitriou received his B.S.in EE from Athens Polytechnic, 1972, a M.S. in EE and Ph.D. in EECS from Princeton, 1974 and 1976 respectively. He is the C. Lester Hogan Professor of EECS. Professor Papadimitriou taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD before joining EECS at UC Berkeley January, 1996. He has authored "Elements of the Theory of Computation", (Prentice-Hall 1982, with Harry Lewis, second edition September 1997), "Combinatorial Optimization: Algorithms and Complexity", (Prentice-Hall 1982, with Ken Steiglitz; second edition by Dover, 1998), "The Theory of Database Concurrency Control", (CS Press 1988), "Computational Complexity", (Addison Wesley, 1994), and "The Undergraduate Textbook Algorithms", (McGraw-Hill 2006, with Sanjoy Dasgupta and Umesh Vazirani). He has also written a novel about computation titled "Turing", (MIT Press 2003).

The boosting approach to machine learning

Robert Schapire, Princeton Abstract: Boosting is a general-purpose, machine-learning method for inferring from data a very accurate classification rule by combining rough and moderately inaccurate "rules of thumb." While rooted in a theoretical framework, boosting has been found to perform quite well empirically. This tutorial will focus on the boosting algorithm AdaBoost, and will explain the underlying theory of boosting, including explanations as to why AdaBoost is often able to generalize well without overfitting the training data. Some of the other theoretical approaches to boosting will be discussed as well, particularly those connecting AdaBoost to fundamental notions from information theory, and to related learning methods based on the maximum-entropy principle. A sampling of practical applications may also be described. Bio: Robert Schapire received his ScB in math and computer science from Brown University in 1986, and his SM (1988) and PhD (1991) from MIT under the supervision of Ronald Rivest. After a short post-doc at Harvard, he joined the technical staff at AT&T Labs (formerly AT&T Bell Laboratories) in 1991 where he remained for eleven years. At the end of 2002, he became a Professor of Computer Science at Princeton University. His awards include the 1991 ACM Doctoral Dissertation Award, the 2003 Gödel Prize and the 2004 Kanelakkis Theory and Practice Award (both of the last two with Yoav Freund). His main research interest is in theoretical and applied machine learning.

Quantum Resistant Cryptography

Umesh Vazirani, UC Berkeley Abstract: Quantum computers, once they are physically realized, will break much of public-key cryptography, including the factoring-based RSA cryptosystem. Is there a good alternative? Research over the last decade into the limits of quantum algorithms has provided a novel possibility: classical cryptography that could be implemented on current computers, but which even quantum computers would not break. In this talk I will describe the evidence that certain computational problems are hard even for quantum computers, as well as some cryptographic implications. Bio: Umesh Vazirani received his B.Tech. in computer science from MIT in 1981 and his Ph.D. in computer science from U.C. Berkeley in 1986. He is currently professor of computer science at U.C. Berkeley and director of BQIC - the Berkeley center for Quantum Information and Computation. Prof. Vazirani is a theoretician with broad interests in novel models of computation. He has done seminal work in quantum computation and on the computational foundations of randomness. He is the author of two books "An introduction to computational learning theory" with Michael Kearns and "Algorithms" with Sanjoy Dasgupta and Christos Papadimitriou.