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.

Behind a sensible computation there lie the 'whys' of each step, which when chained together form a proof that justifies the output. In this sense, efficient computation is tied to short proofs.

This leads to the study of what can or cannot be efficiently proved, i.e., proof complexity. A typical question is this: 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? For a general \(G\), intuition might suggest that a form of brute-force over exponentially many potential colourings is inevitable, 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 boundaries 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