Shuo Pang: Homepage

Hi, I am a lecturer in computer science at the University of Bristol.

I work in computational complexity and discrete math, where a central question is what the limits of efficient computation are. Under every sensible computation there lies a sequence of reasoning: the “why” behind each step of an algorithm, which if chained together form a proof justifying the output. In this sense, efficient computation is tied to the existence of short proofs. This leads to the question of what can or cannot be efficiently proved, i.e., proof complexity.

A typical question looks like this: given a graph \(G\) that has no proper vertex 3-coloring, how hard is it to show this fact? Can it always 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 currently remains beyond reach.

A more realistic goal is to show that 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 mathematics and theoretical computer science. See more

Research Papers

• •Lower bounds for CSP hierarchies through ideal reduction
  Joint with Jonas Conneryd and Yassine Ghannane
• •Truly supercritical trade-offs for resolution, cutting planes, monotone circuits, and Weisfeiler-Leman
  Joint with Susanna De Rezende, Noah Fleming, Duri Janett, and Jakob Nordström
• •Sum-of-Squares lower bound for non-Gaussian component analysis
  Joint with Ilias Diakonikolas, Sushrut Karmalkar, and Aaron Potechin
• •Graph colouring is hard on average for polynomial calculus and Nullstellensatz
  Joint with Jonas Conneryd, Susanna De Rezende, Jakob Nordström, and Kilian Risse
• •SoS lower bound for exact planted clique
• •On CDCL-based proof systems with the ordered decision strategy
  Joint with Nathan Mull and Alexander Razborov (In the journal version page 1396 line 4 "\(i \geq j+2\) and" is a typo to be removed.)
  
• •Large clique is hard on average for resolution

CV