Abstract | ||
---|---|---|
We prove Sylvester-Gallai type theorems for quadratic polynomials. Specifically, we prove that if a finite collection Q, of irreducible polynomials of degree at most 2, satisfy that for every two polynomials Q1,Q2∈ Q there is a third polynomial Q3∈Q so that whenever Q1 and Q2 vanish then also Q3 vanishes, then the linear span of the polynomials in Q has dimension O(1). We also prove a colored version of the theorem: If three finite sets of quadratic polynomials satisfy that for every two polynomials from distinct sets there is a polynomial in the third set satisfying the same vanishing condition then all polynomials are contained in an O(1)-dimensional space.
This answers affirmatively two conjectures of Gupta [Electronic Colloquium on Computational Complexity (ECCC), 21:130, 2014] that were raised in the context of solving certain depth-4 polynomial identities.
To obtain our main theorems we prove a new result classifying the possible ways that a quadratic polynomial Q can vanish when two other quadratic polynomials vanish. Our proofs also require robust versions of a theorem of Edelstein and Kelly (that extends the Sylvester-Gallai theorem to colored sets).
|
Year | DOI | Venue |
---|---|---|
2019 | 10.1145/3313276.3316341 | Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |
Keywords | DocType | Volume |
Arithmetic Circuits, Combinatorics, polynomial identity testing | Conference | abs/1904.06245 |
ISSN | ISBN | Citations |
0737-8017 | 978-1-4503-6705-9 | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Amir Shpilka | 1 | 1095 | 64.27 |