What are efficient algorithms? What are network models? Big Data and Network Sciences have fundamentally challenged the traditional polynomial-time characterization of efficiency and the conventional graph-theoretical characterization of networks.

More than ever before, 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.

For a long time, graphs have been widely used for defining the structure of social and information networks. However, real-world network data and phenomena are much richer and more complex than what can be captured by nodes and edges. Network data are multifaceted, and thus network science requires a new theory, going beyond traditional graph theory, to capture the multifaceted data.

In this talk, I discuss some aspects of these challenges. Using basic tasks in network analysis, social influence modeling, and machine learning as examples, I highlight the role of scalable algorithms and axiomatization in shaping our understanding of "effective solution concepts" in data and network sciences, which need to be both mathematically meaningful and algorithmically efficient.

Shang-Hua Teng is a University Professor and the Seeley G. Mudd Professor of Computer Science and Mathematics at University of Southern California (USC). He has twice won the prestigious Godel 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.

Teng's recent research interests include algorithmic theory (for Big Data), social-choice theory (for Network Sciences), game theory and economics (for understanding the interplay between influence processes and social networks). Dedicated to teach his daughter to speak Chinese as the sole Chinese-speaking parent in an otherwise English-speaking family and environment, he also became fascinated with children's bilingual learning.