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 arising from computation: behind each sensible computation there are the 'whys' of each step, which, if extracted and chained together, form a proof that justifies the output. In this sense, efficient computation is tied to short proofs.

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

A more realistic goal is showing no short proofs exist in restricted formal systems. Many such (nondeterministic) systems capture the reasoning behind widely used algorithms, 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