Shanghua Teng, recently named chairman of the Viterbi School Computer Science department, is a winner of a 2009 Delbert Ray Fulkerson Prize, a high honor presented only every three years.
Teng and collaborator Daniel A. Spielman of Yale University received the honor for their paper on "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time," which appeared in the Journal of the ACM in May 2004.
"The Fulkerson Prize is yet another testimonial to Shanghua's incomparable scholarship in discrete mathematics," said Viterbi School Dean Yannis C. Yortsos. "It is exciting that a scholar of his quality is leading USC Computer Science."
The Mathematical Programming Society (MPS) and the American Mathematical Society (AMS) jointly sponsor the Fulkerson Prizes for outstanding papers in the area of discrete mathematics.
Shanghua Teng
Teng and Spielman attended the ceremony at the the opening session of the 20th International Symposium on Mathematical Programming to receive their commendations, along with checks for $1500.
"Congratulations on your great paper," wrote William Cook, chair of the prize committee.
"The complexity topic of smoothed analysis introduced in this paper has now been applied to many other classes of problems," reads the language of the commendation. "The LP-specific techniques used by Spielman and Teng have interesting interpretations regarding the Hirsh Conjecture and they provide new insights into the good behavior of the simplex algorithm."
Fulkerson Prizes for two other teams were announced at the recent Chicago gathering, the eleventh group given in the history of the prize program, which began in 1979 to honor the memory of the distinguished mathematician whose name it bears.
Teng, a theoretical computer scientist with broad experience in both academia and industry, just joined the USC Viterbi School Department of Computer Science as professor and chair beginning in August, 2009.
Born in Beijing, Teng earned dual undergraduate degrees, a B.S. in computer science and a B.A. in electrical engineering, from Shanghai Jiao Tong University in 1985. Two years later he received a Master's degree from USC and then his Ph.D. from Carnegie Mellon University in 1991, both in computer science.
Since receiving his Ph.D, Teng has distinguished himself through his research and teaching. He was a research scientist at the Xerox Palo Alto Research Center, the NASA Ames Research Center, the IBM Almaden Research Center, Intel Corp., three separate Microsoft research centers and Akamai Technologies.
Immediately before coming to USC, he served as a professor of computer science at Boston University, a research affiliate professor of mathematics at MIT and a visiting professor at Tsinghua University in Beijing. Previously, he held faculty appointments at the University of Illinois at Urbana-Champaign and the University of Minnesota.
Previous honors include an NSF Career Award, a Sloan Fellowship, an IBM award for faculty development and the 2008 Gödel Prize (awarded by ACM) for developing a rigorous framework to explain the practical success of algorithms on real data and real computers that could not be clearly understood through traditional techniques.
