Joint Colloquium Distinguished Lecture Series
Optimization, Learnability, and Games: From the Lens of Smoothed Analysis
 |
Wednesday, December 9, 2009 Shang-Hua Teng |
Abstract:
As the main technical part of this talk, I will discuss one of our recent work on the smoothed analysis of multi-objective optimization. In particular, I will show that the number of Pareto optima in a binary optimization problem with a constant number of linear objective functions is polynomial in the smoothed model. I will also take this opportunity to highlight another recent result on the smoothed analysis of P.A.C. learning. I will then conclude the talk by drawing the contrast between these optimization problems and equilibrium computation in game theory and mathematical economics from the lens of smoothed analysis.
Joint work with Adam Kalai (Microsoft New England Lab), Heiko Roglin (Maastricht University), Alex Samorodnitsky (Hebrew U. ) as well as Daniel Spielman(Yale), Xi Chen (USC), and Xiaotie Deng (City University of Hong Kong).
Biography
SHANG-HUA TENG is the Seeley G. Mudd Professor and Chair of the Computer Science Department at the USC Viterbi School of Engineering. He has taught in Computer Science Departments of Boston University, U. of Minnesota and UIUC and in the Mathematics Department at MIT . He has worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center, Intel, Xerox PARC, Cray Research/SGI, Thinking Machine Corporation, and the NASA Ames Research Center. He received dual B.S. degrees form Shanghai Jiao Tong University in 1985, an M.S. degree in computer science from USC in 1988, and a Ph.D. degree in computer science from Carnegie Mellon University 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, and a recipient of the NSF CAREER 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.
| Return to EECS Joint Colloquium |