COMP 50th Anniversary Distinguished Talk Series - "Intelligent Heuristics Are the Future of Computing?" by Prof. Shang-Hua TENG
Research Seminar
-
Date
23 May 2024
-
Organiser
Department of Computing
-
Time
10:30 - 11:30
-
Venue
TU107, 1/F, Wing TU, PolyU Map
Speaker
Prof. Shang-Hua TENG
Enquiry
Department of Computing 3400 3145 comp50.anniversary@polyu.edu.hk
Summary
Back in 1988, the partial game trees explored by computer chess programs were among the largest search structures in real-world computing. Because the game tree is too large to be fully evaluated, chess programs must make heuristic strategic decisions based on partial information, making it an illustrative subject for teaching AI search. In one of his lectures that year on AI search for games and puzzles, Professor Hans Berliner — a pioneer of computer chess programs — stated:
“Intelligent heuristics are the future of computing.”
As a student in the field of the theory of computation, I was naturally perplexed but fascinated by this perspective. I had been trained to believe that “Algorithms and computational complexity theory are the foundation of computer science.” However, as it happens, my attempts to understand heuristics in computing have subsequently played a significant role in my career as a theoretical computer scientist. I have come to realize that Berliner’s postulation is a far-reaching worldview, particularly in the age of big, rich, complex, and multifaceted data and models, when computing has ubiquitous interactions with science, engineering, humanity, and society.
In this talk, I will share some of my experiences on the subject of heuristics in computing, presenting examples of theoretical attempts to understand the behavior of heuristics on real data, as well as efforts to design practical heuristics with desirable theoretical characterizations. My hope is that these theoretical insights from past heuristics — such as spectral partitioning, multilevel methods, evolutionary algorithms, and simplex methods — can shed light on and further inspire a deeper understanding of the current and future techniques in AI and data mining.
Keynote Speaker
Prof. Shang-Hua TENG
University Professor and Seeley G. Mudd Professor of Computer Science and Mathematics
Viterbi School of Engineering
University of Southern California
USA
Prof. Shang-Hua Teng is a University Professor and Seely G. Mudd Professor of Computer Science and Mathematics at USC. He is a fellow of SIAM, ACM, and Alfred P. Sloan Foundation, and has twice won the Gödel Prize, first in 2008, for developing smoothed analysis, and then in 2015, for designing the breakthrough scalable Laplacian solver. Citing him as, “one of the most original theoretical computer scientists in the world”, the Simons Foundation named him a 2014 Simons Investigator to pursue long-term curiosity-driven fundamental research. He also received the 2009 Fulkerson Prize, 2023 Science & Technology Award for Overseas Chinese from the China Computer Federation, 2022 ACM SIGecom Test of Time Award (for settling the complexity of computing a Nash equilibrium), 2021 ACM STOC Test of Time Award (for smoothed analysis), 2020 Phi Kappa Phi Faculty Recognition Award (2020) for his book Scalable Algorithms for Data and Network Analysis, 2011 ACM STOC Best Paper Award (for improving maximum-flow minimum-cut algorithms). In addition, he and collaborators developed the first optimal well-shaped Delaunay mesh generation algorithms for arbitrary three-dimensional domains, settled the Rousseeuw-Hubert regression-depth conjecture in robust statistics, and resolved two long-standing complexity-theoretical questions regarding the Sprague-Grundy theorem in combinatorial game theory. For his industry work with Xerox, NASA, Intel, IBM, Akamai, and Microsoft, he received fifteen patents in areas including compiler optimization, Internet technology, and social networks. Dedicated to teaching his daughter to speak Chinese as the sole Chinese-speaking parent in an otherwise English-speaking family and environment, he has also become fascinated with children's bilingual learning.
