Logo: University of Southern California

Shang-Hua Teng Returns to Research After Productive Term as CS Department Chair

Prizewinning algorithm theorist looks forward to concentrating on computer science
Eric Mankin
July 03, 2012 —

After dedicating three years to leading the USC Viterbi School Computer Science Department, Dr. Shang-Hua Teng is passing the torch to the new CS Chair, Professor Gaurav Sukhatme, and will enter the next phase of his career as the Seely G. Mudd Professor of Engineering.

Shang-Hua Teng
"The Department has enjoyed tremendous growth and success under Shang-Hua’s leadership," said Yannis C. Yortsos, the Dean of Viterbi School of Engineering.

Under this leadership, the Computer Science Department greatly transformed its makeup with the addition of five brilliant young faculty members, Yan Liu (CMU), Ethan Katz-Bassett (UW), Minlan Yu (Princeton), Shaddin Dughmi (Stanford) and Hao Li (ETH Zürich). The new recruits, Teng said, were part of a broadening of focus of the department, building in four strategic areas: Data & Machine Learning, Networks & Systems, Theoretical Computer Science & Game Theory, and Computer Graphics & Interactive Technologies.

"I have learned a great deal not only about being a chair, but also about my own discipline,” reflected Teng. “My colleagues from all areas of computer science taught me so much in these last three years that I feel that I just received a second degree in computer science, or more generally in the field of computing. I believe I am now a better computer scientist, if not a better theoretician, from learning their work and areas of research."

With this renewed knowledge, the winner of two of the highest honors in the area, the 2008 Gödel Prize and the 2009 Fulkerson Prize, is eager to give complete focus back to his research, which is at the intersection of theoretical computer science, game theory, and mathematical programming.

Since coming to USC in the summer of 2009, Teng has been conducting research in two broad threads; both focused on analyzing fundamental optimization problems and determining the most efficient ways for computers to solve them. 

His first research direction is supported by an NSF large collaborative grant, "Algebraic Graph Algorithms: The Laplacian and Beyond" that he and collaborators Jonathan Kelner of MIT and Daniel Spielman of Yale received in 2011. This line of research was initiated by Teng and Spielman’s groundbreaking algorithm in 2004 that can solve a particular family of linear systems that arise in network analysis. Building on this breakthrough, last year, Teng and his collaborators Paul Christiano (MIT), Kelner, Aleksander Madry (MIT), and Spielman developed the fastest known approximation algorithm for one of the most basic problems in computer science, called maximum flow.

Erica Klarreich recently published an extremely clear and recent account of how Shang-Hua Teng and Daniel Spielman's insights created a revolutionary new breed of ultrafast computer algorithms that offer computer scientists a novel tool to probe the structure of large networks. To read the story, published by the Simons Foundation, click on the image.
Their work, “Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs” was hailed as the “first improvement of this fundamental algorithm in 10 years” (http://web.mit.edu/newsoffice/2010/max-flow-speedup-0927.html) and won the best paper award at the prestigious theory conference ACM Symposium on Theory of Computing (STOC). In the recent SIAM Data Mining Conference in Anaheim, Teng outlined his ideas for further expanding this direction of research for data and network analysis in his invited presentation, “Algorithmic Primitives for Network Analysis: Through the Lens of the Laplacian Paradigm.”

His second research direction has been supported by an NSF medium grant, titled "Smoothed Analysis in Multi-Objective Optimization, Machine Learning, and Algorithmic Game Theory" that he won in 2010. This is an interdisciplinary program that attempts to develop rigorous theory for understanding fast, practical algorithms that are used in areas including economic pricing, strategic planning, and artificial intelligence.

"There is a rumor that being a department chair will hurt one's research," said Teng. "I will do my best to disprove it." Teng is eager to see if his "second CS degree" will help to accelerate and further broaden his research.