Logo: University of Southern California

Beautiful Problems, Fast Solutions

Shang-Hua Teng, a two-time Gödel Prize winner, improves algorithm efficiency.
By: Kathleen Concialdi
March 16, 2016 —
Shang-Hua Teng, Steely G. Mudd Professor of computer Science and Mathematics, won the 2015 Gödel Prize.

Shang-Hua Teng sees beauty in mathematics.

His office wall covered in numerical calculations, Teng, the Seeley G. Mudd Professor of Computer Science and Mathematics, speaks passionately about solving problems and finding patterns. “There are many problems that have a good enough solution, but not a fast solution,” said Teng.

It is that desire to find a solution to creating faster solutions, for example, that earned Shang-Hua, along with longtime collaborator and friend, Daniel Spielman of Yale, the 2015 Gödel Prize for their work in improving the efficiency of graph algorithms.

The Gödel prize, named after famed mathematician and philosopher Kurt Gödel, is awarded annually by both the Association for Computer Machinery (ACM) Special Interest Group on Algorithms and Computation Theory and the European Association for Theoretical Computer Science (EATCS), and this is the second such award for Teng and Spielman, 2008 winners for their work on the smoothed analysis of algorithms.

Last year, they won for their series of papers that Teng describes as the interface between numerical non-linear algebra and graph theory, addressing the efficiency of graph algorithms and discovering how to make them faster and more efficient. “There is huge talk about Big Data, initiated by the Internet, and as a result, computationally, people need faster algorithms.” And, Teng noted, “As theoreticians, we want to solve problems as fast as we can.”

Graphs are what mathematicians call the structure of a network. Imagine string pulled across tacks on a flat board, each point that the strings touch a tack is a node and multiple strings on a tack are the networks, the entire board is called a graph. Graph theory is the mathematical study of these graphs.

Researchers, including some of Teng’s former students, have applied graph theory and numerical non-linear algebra to Internet issues, such as detecting spam and analyzing Google page ranks.

The landscape of computer science is rapidly changing and has motivated Teng to explore less traditional computer science notions. Currently, he is drawn to community identification and determining mathematically whether a community is a strong community — a play on Social Cognitive Theory’s (SCT) concept of preference aggregation, summarizing individual preferences into a final, simple result.

Teng illustrates this idea by considering an election with candidates to rank. How can individual preference be converted into a summarization of the group to determine strong community choice? If you were to analyze Facebook, you would find a network of people, where a handful of people lean left, a handful lean right, and there is a group whose leanings are unknown. There may be some overlap as people in the same network may have shared leanings. Considering each individual’s personal preference, individual agendas, and histories, how can you tell if the community is more likely to vote for a particular candidate?

Teng illustrates this theory in another way, by looking at his own Department of Computer Science. “Is my department a good community?” he asks. “If we look at things like the members’ online presence, individual preferences, and individual histories and say this group is a good community, how do you determine this mathematically?”

Teng believes that there is a mathematical way to convert individual preference into a clear summarization and determine whether a community is a good one. “Social Cognitive Theory has the framework and has been happening since the beginning of democracy. The phenomenon is largely unexploited, and I am interested to at least see mathematically how to identify patterns.”