Title: Sylvester-Gallai type configurations and Polynomial Identity Testing
| Speaker: | Akash Sengupta |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: The classical Sylvester-Gallai theorem in combinatorial geometry says the following:
If a finite set of points in the Euclidean plane has the property that the line joining any two points contains a third point from the set, then all the points must be collinear.
More generally, a Sylvester-Gallai (SG)-type configuration is a finite set of geometric objects with certain local dependencies. A remarkable phenomenon is that the local constraints give rise to global dimension bounds for linear SG-type configurations, and such results have found far reaching applications to complexity theory and coding theory. In particular, SG-type configurations have been extremely useful in applications to Polynomial Identity Testing (PIT), a central problem in algebraic complexity theory.
In this talk, we will discuss non-linear generalizations of SG-type configurations which consist of polynomials. We will discuss how uniform bounds on SG-configurations give rise to deterministic poly-time algorithms for the PIT problem. I’ll talk about results showing that these non-linear SG-type configurations are indeed low-dimensional as conjectured by Gupta in 2014. This is based on joint works with A. Garg, R. Oliveira and S. Peleg.