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, with a focus on lower bounds in proof complexity.

Here is an example of the type of questions I enjoy exploring: Given a graph \(G\) with no proper vertex 3-coloring, does this fact admit proofs of length at most \(|G|^{10}\)? For an arbitrary such \(G\), intuition might suggest that some form of brute-force search over exponentially many potential colorings is inevitable and the answer should be no. Yet a rigorous argument remains beyond reach.

A more realistic goal is to show that short proofs do not exist within certain formal deductive systems. Since many of these systems capture the “methods of reasoning” used by popular algorithms, the lower bounds are relevant to computer science. The techniques developed to establish them are distinctive but connected to many areas of math and TCS. See more

Research Papers