Shuo Pang: Homepage

Hi, I am a lecturer in computer science at the University of Bristol. I work in computational complexity and discrete mathematics, focusing on lower bounds in proof complexity.

Here's an example of questions I like exploring: given a graph \(G\) that has no proper vertex 3-coloring, does this fact admit proofs of length \(\leq |G|^{10}\)? For an arbitrary such graph \(G\), intuition might suggest that some form of brute-force search over exponentially many potential colorings is inevitable so the answer should be no. But a rigorous proof remains beyond reach.

A more realistic goal is to show that short proofs do not exist in restricted formal systems. Many such systems capture the “methods of reasoning” behind popular algorithms, so results on their reasoning efficiency (upper and lower bounds) are relevant to computer science. The techniques for obtaining these results are distinctive but connected to many areas of math and TCS. See more

Research Papers

• •Lower bounds for CSP hierarchies through ideal reduction
  Joint with Jonas Conneryd and Yassine Ghanne
• •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 journal version "\(i \geq j+2\) and" on page 1396 line 4 is a typo to be removed.)
  
• •Large clique is hard on average for resolution

CV