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
Research Papers
With AI
- •
Without AI
- • With Jonas Conneryd, Yassine Ghannane, Jakob Nordström, Kilian Risse, Dmitry Sokolov.
- • With Jonas Conneryd, Yassine Ghannane.
- • With Susanna De Rezende, Noah Fleming, Duri Janett, Jakob Nordström.
- • With Ilias Diakonikolas, Sushrut Karmalkar, Aaron Potechin.
- • With Jonas Conneryd, Susanna De Rezende, Jakob Nordström, Kilian Risse.
- •
- • A typo "\(i \geq j+2\) and" to be removed from page 1396 line 4 of the journal version.
With Nathan Mull, Alexander Razborov. - •