Abstract: In the age of network sciences and machine learning, efficient algorithms are now in higher demand more than ever before. Big Data fundamentally challenges the classical notion of efficient algorithms: Algorithms that used to be considered efficient, according to polynomial-time characterization, may no longer be adequate for solving today’s problems. It is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation. Using several basic tasks in network analysis, social influence modeling, machine learning, and optimization as examples – in this talk – I will highlight a family of fundamental algorithmic techniques for designing provably-good scalable algorithms.

Bio: Shang-Hua Teng is the University Professor and Seeley G. Mudd Professor of Computer Science and Mathematics at University of Southern California. He has twice won the prestigious Gödel Prize in theoretical computer science, first in 2008, for developing the theory of smoothed analysis , and then in 2015, for designing the groundbreaking nearly-linear time Laplacian solver for network systems. Citing him as, “one of the most original theoretical computer scientists in the world”, the Simons Foundation named Teng a 2014 Simons Investigator, for pursuing long-term curiosity-driven fundamental research. Prior to joining USC in 2009, he was a professor at Boston University. He has also taught at MIT, the University of Minnesota, and the University of Illinois at Urbana-Champaign. He has worked at Xerox PARC, NASA Ames Research Center, Intel Corporation, IBM Almaden Research Center, Akamai Technologies, Microsoft Research Redmond, Microsoft Research New England and Microsoft Research Asia. Teng is a Fellow of the Association for Computing Machinery (ACM), as well as an Alfred P. Sloan fellow.