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 math, where a big question is the limit of efficient computation.

Note that behind every sensible computation there are the 'whys' of each step, which, if 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, or proof complexity. A typical question is like this: given a graph \(G\) that cannot be vertex 3-coloured, how hard is it to show 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 to show there is no short proof in restricted formal systems. Many of these (nondeterministic) systems capture the reasoning behind widely used algorithms, so understanding their efficiency matters.

The techniques involved have a distinctive flavour but are well-connected to several branches in math and TCS. See more

Research Papers