Shuo Pang: Homepage
Hi, I am a lecturer in computer science at the University of Bristol, UK.
I work in computational complexity and discrete mathematics, broadly on the limits of efficient computation.
My main focus is on proof complexity
... which studies what can/cannot be efficiently proved. Behind an algorithm there are proofs: the 'whys' behind each computation step, if formalized and chained, yield a proof that justifies the output. If moreover the computation is efficient, the proof is expected to be short.
An example question: given a graph \(G\) that is not 3-colourable, how hard is it to prove this fact? Is there always a proof in \(|G|^{10}\) steps in ZFC? Intuition may suggest that there can be some graph which is non-3-colourable but which avoids all 'easy evidences' like containment of 4-cliques, as sparse random graphs do, and for such graphs every proof has to brute force some exponential family of partial colourings*. A rigorous argument, however, remains beyond reach.
A more realistic goal is showing no short proof exists in restricted formal systems. Despite being restricted, many such systems (resolution, Gröbner bases, cutting planes, sum-of-squares, etc.) capture powerful methods in combinatorial optimisation and automated reasoning. Understanding their strength and limitations matters.
The techniques involved have a distinctive flavour, but they are well-connected to several branches in math and TCS. See more
- • A degree–size relation for resolution over polynomials
2026 - • On the power of polynomial calculus over non-Boolean domains
With Jonas Conneryd, Yassine Ghannane, Jakob Nordström, Kilian Risse, Dmitry Sokolov. 2026 - • Lower bounds for CSP hierarchies through ideal reduction
With Jonas Conneryd, Yassine Ghannane. 2025 - •Truly supercritical trade-offs for resolution, cutting planes, monotone circuits, and Weisfeiler-Leman
With Susanna De Rezende, Noah Fleming, Duri Janett, Jakob Nordström. 2025 - •Sum-of-Squares lower bound for non-Gaussian component analysis
With Ilias Diakonikolas, Sushrut Karmalkar, Aaron Potechin. 2024 - •Graph colouring is hard on average for polynomial calculus and Nullstellensatz
With Jonas Conneryd, Susanna De Rezende, Jakob Nordström, Kilian Risse. 2023 - •SoS lower bound for exact planted clique
2021 - •On CDCL-based proof systems with the ordered decision strategy
A typo "\(i \geq j+2\) and" to be removed from page 1396 line 4 of the journal version.
With Nathan Mull, Alexander Razborov. 2019 - •Large clique is hard on average for resolution
2019
Research Papers
With AI
Pre-AI