Introduction to Geometric Complexity Theory by Christian Ikenmeyer

Introduction to Geometric Complexity Theory by Christian Ikenmeyer

Explore the foundations of Geometric Complexity Theory in this lecture from the Workshop on Algebraic Complexity Theory. Delve into the algebraic approach to computational complexity, focusing on the VP vs VNP question as an analogue to the classical P vs NP problem. Learn about the key areas of study in algebraic complexity, including lower bounds for explicit polynomials, polynomial identity testing, and circuit reconstruction. Gain insights into recent advances in the field, the deep connections between different problem areas, and potential barriers to solving general complexity questions. Suitable for students and researchers interested in theoretical computer science and computational algebra.