Abstract: The advent of the Internet has enabled a tremendous growth of online markets and social computing. It has also made clear that modern computing systems need to incorporate an understanding of human behavior and preferences into their design. Towards this goal, my work explores the interaction of Theoretical Computer Science with Economics and Learning.
In the first part of my talk, I will show how my work has used an algorithmic approach to push the boundary of auction theory. I will present an extension of Myerson's celebrated work to the design of multi-item revenue optimal auctions. I will also provide a sweeping generalization of the celebrated Milgrom and Weber "linkage principle."
In the second part of my talk, I will turn to Learning, showing how the algorithmic perspective can help towards understanding the efficiency of existing methods and towards designing novel learning algorithms with provable performance guarantees. I will present the first global convergence analysis for the widely used Expectation-Maximization heuristic for learning mixtures of Gaussians, and will develop finitary central limit theorems and optimal learning algorithms for Poisson-Multinomial Distributions.
Short Bio: Christos is a PhD Student with Costis Daskalakis in the Theory of Computation group at MIT. Prior to joining MIT, he completed his undergraduate studies in EECS at the National Technical University of Athens, where he did research with Prof. Dimitris Fotakis. His research interests include algorithmic game theory and learning theory, and more broadly the design, analysis and theory of algorithms. During his time at MIT, Christos spent two summers interning at Google and Yahoo Labs and has mentored two high school students in AGT research through the MIT PRIMES program. Christos is the recipient of the Simons Graduate Award in Theoretical Computer Science and his research has received the best paper award at the 2013 ACM Conference on Economics and Computation.