The P vs NP question is arguably the most fundamental problem in computational complexity theory. Posed in the 70's by Stephen Cook and Leonid Levin it has long tantalized the world's top computer scientists in their effort to understand the power of polynomial time Turing machines.
In 1979, Leslie Valiant proposed an algebraic analogue of this problem, the VP vs VNP problem. The computational models in this setting are algebraic circuits evaluating multivariate polynomials. The quintessential problem here being whether the permanent of an m x m matrix is the determinant of an n x n matrix whose entries are affine linear forms in the m^2 variables of the permanent, when n is subexponential in m. It is known that a prerequisite to solving the P vs NP problem (in the non-uniform setting) is to solve the VP vs VNP problem.
Even though there has been tremendous progress in our understanding of algebraic circuits, the fundamental lower bound problem remains elusive. Geometric Complexity Theory was proposed by Ketan Mulmuley and Milind Sohoni as a possible approach to settling this question. In this setting the VP versus VNP problem is posed as a problem of separating the orbit closures of two forms in projective space equipped with a natural action of the general linear group. Viewed through the lens of GCT, the VP versus VNP problem makes connections to classical invariant theory, representation theory and algebraic geometry. Although far from achieving its desired goal, GCT has given rise to a number of interesting problems at the intersection of algebraic complexity and algebraic geometry. Recently there has been progress on solving some of these problems using algebraic methods and also methods from optimization theory.
The GCT2022 workshop hopes to bring researchers working in the diverse fields of algebraic circuits, algebraic geometry, representation theory and optimization theory under one common umbrella. The aim is to expose students and young researchers to the fascinating connections between these areas by studying problems arising from algebraic complexity theory and solutions to some of these problems.
With a view to making GCT accessible to a larger audience we are planning an online series of expository lectures covering algebraic complexity, algebraic geometry, algebraic groups, representation theory and optimization theory which arise in GCT. This will be followed by an onsite meeting in Chennai from Jan 17 to Jan 22, 2022 where more advanced topics will be discussed. The conference will be held from Jan 24 to Jan 28, 2022. Due to the current sanitary situation, the workshop and conference will be replaced by a 100% virtual event. Further details can be found on the Program page.
If you are interested in attending gct2022 (either the online series, or the onsite series, or both) please register by following the registration link and send an email to gct2022@sciencesconf.org
Poster
Consider sharing the event's poster to share with potential participants!
Organising committee
Organisers:
Thomas Seiller (CNRS and Sorbonne Paris Nord University)
Loading... 
