Computer Science/Discrete Mathematics Seminar II

The following multi-determinantal algebraic variety plays an important role in algebra 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? To address this we will use ideas and techniques from various algebraic, geometric, and combinatorial fields. As always, no background will be assumed. This is joint work with Avi Wigderson.