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 shortly proved. Proofs underlie algorithms: 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.
Example: 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 some graphs are non-3-colourable but avoid all 'easy evidences' like the containment of 4-cliques, as sparse random graphs do, and that for such a graph 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 some restricted formal systems. Despite (and because of) being restricted, these systems capture powerful methods in combinatorial optimisation and automated reasoning; these include resolution, Gröbner bases, cutting planes, sum-of-squares, etc. 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
Without AI