Dr Shuo Pang
BSc, MSc, PhD
Expertise
I research computational complexity and discrete math, with a focus on proof complexity.
Current positions
Lecturer in Algorithms and Complexity
School of Computer Science
Contact
Press and media
Many of our academics speak to the media as experts in their field of research. If you are a journalist, please contact the University’s Media and PR Team:
Research interests
I study impossibility results ("lower bounds") that show fundamental computational problems require exponential running time for popular types of algorithms. This motif is mathematically distilled and explored in the field of proof complexity, using techniques from combinatorics, logic, and circuit and communication complexity, with results often applicable to areas such as combinatorial optimization and learning theory.
Publications
Recent publications
15/06/2025Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler–Leman
STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)
On CDCL-Based Proof Systems with the Ordered Decision Strategy
SIAM Journal on Computing
Large Clique is Hard on Average for Resolution
Computer Science – Theory and Applications