Algebraic Proof Complexity Explained: A Beginner-Friendly Introduction 🧠

Toni Pitassi and Josh Grochow – Algebraic Proof Complexity: a gentle introduction

This session is aimed at introducing researchers in other areas of theory to algebraic (and semi-algebraic) proof complexity, and to the wealth of open problems and connections with algebraic circuit complexity, polynomial identity testing, and inapproximability.

Part I: Motivation, history, and introduction to algebraic proof complexity (Toniann Pitassi)

This first talk will give a quick primer on proof complexity, especially as it relates to algebraic proof systems. It will cover some of the history and motivation that led to the study of algebraic proof systems, as well as introduce some well-studied algebraic proof systems and the relations between them.

Part II: Circuit complexity, ideals and proof systems: connections and recent results (Joshua A. Grochow)

The second talk will cover connections between the Ideal Proof System (IPS), circuit complexity, and more generally complexity in ideals. In particular, it will cover the relation between IPS and VP vs VNP, as well as the recent result of Andrews & Forbes that extends the constant-depth algebraic circuit lower bound of Limaye-Srinivasan-Tavenas to a lower bound on refuting certain polynomial equations in IPS. The talk will highlight the connection between algebraic circuit complexity, algebraic proof complexity, and even Boolean circuit complexity to the complexity not of individual (families of) polynomials, but of arbitrary (families of) polynomials inside an ideal or coset of an ideal.