Shuo Pang: Homepage

s.(last name)@bristol.ac.uk

Hi, I am a lecturer in computer science at the University of Bristol.

I work in computational complexity and discrete mathematics, broadly on the limits of efficient computation.

My focus is on proof complexity, which studies what can or cannot be efficiently proved. Proofs are natual objects tied to computation: behind every sensible computation there are the 'whys' of each step, which, if formalized and chained together, form a proof justifying the computation output. If moreover the computation is efficient, the proof is expected to be short.

Here's an example question: given a non-3-colourable graph, how hard is it to prove this fact? For example, can it be proved in \(|G|^{10}\) steps? Intuition might suggest that for a "generic" \(G\), every possible proof requires some form of brute-force over exponentially many potential colourings; yet, a rigorous argument remains beyond reach.

A more realistic goal is establishing that no short proof exists in restricted formal systems. Many such systems (e.g., resolution, polynomial calculus, cutting planes, sum-of-squares, and more) capture widely used methods combinatorial optimisation and automated reasoning, so understanding their power and limitations matters.

The techniques involved have a distinctive flavour, but they are well-connected to several branches in mathematics and theoretical computer science. SEE MORE

Research Papers