MPS Awardee Spotlight: Shang-Hua Teng

Shang-Hua Teng is a 2014 Simons Investigator in theoretical computer science. Teng is the Seeley G. Mudd Professor of Computer Science and Mathematics at the University of Southern California. He is a two-time recipient of the Gödel Prize in theoretical computer science, in 2008 and 2015, for his joint work with longtime collaborator Dan Spielman of Yale University.

Shortly after finishing his Ph.D. in computer science at Carnegie Mellon University, Teng was invited to write a simulator for Intel Corporation’s Pentium processor. “Going through that allowed me to see several graph algorithms and data structures in large-scale applications that I had never seen before.”

His algorithms were later implemented at the International Business Machines Corporation and at NASA Ames Research Center. He has also worked and consulted for Microsoft Research, Akamai, IBM Almaden Research Center and Xerox PARC. At NASA, the parallel load-balancing algorithm helped separate weather simulations and earthquake simulations into independent components, which made it possible to implement them on many machines simultaneously. At the end of the project, one of the NASA Advanced Supercomputing Division Parallel Benchmark leaders, Horst Simon (now the deputy director of the Lawrence Berkeley National Laboratory) suggested to Teng and Spielman they prove a theorem formalizing the encountered issues. That prompt lead to Teng and Spielman’s early work on spectral partitioning, an application that continues to inspire Teng’s computer science research.

Teng is interested in developing new algorithmic theories in the age of big data. “While the notion of asymptotic complexity has been established for over 50 years, I think the internet really forces us to focus on asymptotic problems. In the age of big data, the number of input sites is very large — essentially infinite — and the costs of computing increase dramatically with the growing size of the problems. Polynomial-time algorithms are no longer efficient.” Teng works to understand the theories behind scalable algorithms for data- and network-analysis algorithms, whose running time is essentially linear. “In this domain we continue to discover new techniques, of how to make input smaller and sparser, and how to locally understand the network of data so we can compute a global solution. There have been some very beautiful developments in this direction.”

Today, network data is extremely complex, and Teng is keen to describe the multilayered parts of networks and to define mathematical concepts that capture the interactions between multifaceted, complex data. For example, he considers the impact of social influence on the underlying network topology, or the “interplay between dynamics and network.” He says, “If you look at Twitter, it’s not just a graph; it’s a dynamical process happening on a graph. If you look at how social networks engage and at how people attempt to use these networks, for personalized advertisements and so on, clearly, this is no longer a just a graph.” Teng also cites social choice theory as an area of influence: “This impacts some of my current work, and I find it exciting because it’s so new to me.”

Partnerships between academia and industry have shaped Teng’s career and have influenced his research and teaching. Teng is known for his interdisciplinary approach to teaching and encourages students to apply theoretical thinking to real-world problems. His cryptography course incorporates game theory, computing and economics. He enjoys receiving emails from students years later, explaining how his courses have helped them make connections in their own work.

Teng is also interested in language and learning theory. Watching his four-year-old daughter grow up speaking Chinese and English has inspired Teng to think about machine learning and statistical learning theory. “It’s been fascinating to watch bilingual, multilingual formations — how does one simultaneously acquire multiple languages, and how do these interact with each other? How much does it change your view of the world?”