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.

Under every sensible computation lie the 'whys' of each step, whose chaining together form a proof that justifies the final output. In this sense, efficient computation is tied to short proofs. This leads to the question of what can or cannot be efficiently proved, or proof complexity.

A typical question looks 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 some 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