Building a web application that can handle sudden popularity and growth is an important challenge - techniques that work well when you have thousands of users suddenly start causing problems when you reach millions of users, or when your site shows up on the front page of Reddit and you suddenly have thousands of new signups every minute. The power and flexibility of relational databases (e.g., SQL databases) becomes a burden as the costs of scaling a database starts to grow superlinearly, leading to the recent popularity of so-called non-relational databases / distributed key-value stores. I’ll talk about Google’s approach, including its internal database called Bigtable, and the public App Engine interface that anyone can use to build highly scalable web apps. I’ll also talk about opportunities for summer internships at Google.

The speaker, Dominic Mazzoni, got his B.S. in Mathematics from Harvey Mudd in 1999 and his M.S. in Computer Science from Carnegie Mellon in 2001. He is the original author of Audacity, the open-source cross-platform audio editor, which has been downloaded over 100 million times and is still under active development. From 2001 until 2006 he worked in the Machine Learning group at the NASA Jet Propulsion Lab in Pasadena, using advanced computer science methods to automate mundane science data analysis tasks. Since 2006 he has been working at Google in the Santa Monica office, working on text processing software for Google’s AdSense for three years, and more recently on an Accessibility engineering team that improves access for people with disabilities. His current side project, Ringdroid, a mobile phone ringtone editor, is at the top of the Android marketplace and has been downloaded onto over a million Android phones. He has co-authored 19 peer-reviewed publications and an e-book.

I will present some recent advances in Algorithmic Game Theory. I will focus on the computational equivalence of Nash equilibria for games, Arrow-Debreu equilibria and Fisher equilibria for markets, and fractional equilibria for networks. In additional to worst-case complexity, I will consider the smoothed and approximation complexity of these problems. If time permits, I will highlight some potential computational difference between solution concepts in games and in multi-objective optimization.

Joint work with Xi Chen, Xiaotie Deng, Deichen Dai, Ye Du, Li-Sha Huang, Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Heiko Röglin, Ravi Sundaram and Paul Valiant.

Shang-Hua Teng is the Seeley G. Mudd Professor and the Chairman of the Computer Science Department at USC Viterbi School of Engineering. He taught as a faculty in the Department of Mathematics of MIT and in the Computer Science Departments of Boston University, the University of Minnesota and UIUC. He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel Corporation, Xerox PARC, Cray Research/SGI, Thinking Machine Corporation, and NASA Ames Research Center. He received a dual B.S. degree in computer science and in electrical engineering from Shanghai Jiao Tong University in 1985, a M.S. degree in computer science from University of Southern California (USC) in 1988, and a Ph.D. degree in computer science from Carnegie Mellon University (CMU) in 1991.

He is a recipient of the 2009 Fulkerson Prize (AMS-MPS) and the 2008 Gödel Prize (ACM-EATCS) for his joint work on Smoothed Analysis of Algorithms with Daniel Spielman. He is also an ACM Fellow, Alfred P. Sloan Fellow, winner of Senior Xerox Award for Outstanding Faculty Research (UIUC), and has received NSF Faculty Early Career Development Award. His recent research interests include computational game and economics theory, spectral graph theory, scientific computing, and mathematical programming. He has received more than ten US Patents for his work on compiler optimization and Internet technology.