Penn Arts & Sciences Logo

CAGE: Philadelphia Area Combinatorics and Alg. Geometry Seminar

Thursday, October 31, 2019 - 3:00pm

Visu Makam

Institute of Advanced Study


University of Pennsylvania


The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: SING(n,m), consisting of all m-tuples of n x n complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING(n,m) will imply super-polynomial circuit lower bounds, a holy grail of the theory of computation. 
A sequence of recent works suggests such efficient algorithms for memberships in a general class of algebraic varieties, namely the null cones of linear group actions. Can this be used for the problem above? Our main result is negative: SING(n,m) is not the null cone of any (reductive) group action! This stands in stark contrast to a non-commutative analog of this variety, and points to an inherent structural difficulty of SING(n,m).
This is joint work with Avi Wigderson.