It is a distinct honour to welcome Prof. Shang-Hua Teng, University Professor and Seeley G. Mudd Professor of Computer Science and Mathematics at the University of Southern California, as the keynote speaker in the CDS Distinguished Lecture Series. Prof. Teng will present a lecture entitled “P+P ≧ PSPACE: Deep Logic, Strategic Losing, and Game Secrets”.

Speaker:

Prof. Shang-Hua Teng  
University Professor and Seeley G. Mudd Professor of Computer Science and Mathematics  
University of Southern California 

Date:

30 January 2026 (Friday) 

Time:

3:30pm – 4:30pm 

Venue:

HW312, Haking Wong Building, The University of Hong Kong 

Abstract:
A combinatorial game is defined by a ruleset specifying positions and feasible moves. In the normal-play setting, two players alternate moves, and the player forced to play at a terminal position—where no moves remain—loses. Optimal play often requires deep strategic reasoning and is typically PSPACE-hard. In Combinatorial Game Theory (CGT), the disjunctive sum of two games GGG and HHH, denoted G+HG + HG+H, allows the next player to move in exactly one component game.  

   

In this talk, Prof. Teng shows that the sum of two polynomial-time solvable games can be PSPACE-hard. In other words, P + P ≥ PSPACE, where P and PSPACE represent families of polynomial-time and polynomial-space solvable games, and “+” denotes the disjunctive sum. This contrasts with classical Sprague-Grundy Theory (1930s), which states that the Grundy value of the sum of impartial games can be computed in polynomial time. Assuming PSPACE ≠ P, he proves there is no general polynomial-time method to combine two polynomial-time solvable impartial games to efficiently solve the sum. The results settle two long-standing complexity questions in CGT, open since 1981 and 1993. He will also draw a connection between the theorem and a famous Chinese idiom honouring strategist Zhuge Liang(諸葛亮) from The Romance of the Three Kingdoms(三國演義).  

   

Joint work with Kyle Burke (Florida Southern College) and Matt Ferland (Dickinson College).  

Biography:

Shang-Hua Teng is a USC University Professor of Computer Science and Mathematics. 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 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, 2021 and 2025 ACM STOC Test of Time Awards (for smoothed analysis and max-flow computation), and 2022 ACM SIGecom Test of Time Award (for settling the complexity of computing a Nash equilibrium. In addition, he co-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, and was recently named a fellow of the National Academy of Inventors. 

All are welcome to attend.