PhD Seminar • Algorithms and Complexity • Radical Sylvester-Gallai Theorem for Tuples of Quadratics

Please note: This PhD seminar will take place in DC 3317.

Abhibhav Garg, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Rafael Oliveira

The classical Sylvester-Gallai theorem states that given any finite sets of points such that the line joining any two points passes through a third point, the set of points must be colinear. There are a number of generalisations of this theorem that have been studied, with applications in algebraic complexity and coding theory. Hansen generalised the theorem by showing that if the linear space spanned by any k points contains at least k+1 points, then the set of points lie in a low dimensional affine subspace. This result has applications in PIT for depth three circuits. Motivated by this application to PIT, Gupta introduced a non-linear generalisation of Sylvester-Gallai configurations and showed that bounding the dimensions of such configurations would imply polynomial time PIT for depth four circuits. The dimension two case for quadratic Sylvester Gallai configurations was shown to have constant dimension by Shpilka. In this work, we prove a dimension k version of this theorem, simultaneously generalising the results of Hansen and Shpilka. 

This is joint work with Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta.