A useful corollary of the famous Sylvester-Gallai theorem, which found many applications in theoretical computer science, states that if a finite set of linear forms L satisfy that for every two forms, L1, L2 ∈ L there is a subset I ⊂ L, such that L1, L2 ∈ I and whenever L1 and L2 vanish then also ∏i∈I Li vanishes, then the linear span of L has dimension at most 3. This corollary is used to achieve deterministic algorithms for certain depth-3 polynomial identities and to bound performance of locally correctable codes. In this work we prove that if a finite set of irreducible quadratic polynomials Q satisfy that for every two polynomials Q1,Q2 ∈ Q there is a subset I ⊂ Q, such that Q1,Q2 ∈ I and whenever Q1 and Q2 vanish then also ∏i∈I Qi vanishes, then the linear span of the polynomials in Q has dimension O(1). This extended an earlier result, that showed a similar conclusion when |I| = 1. This result brings us one step closer towards obtaining a polynomial time deterministic algorithm for the polynomial identity question of certain depth-4 identities. To obtain our main theorem we prove a new result classifying the possible ways that a product of quadratic polynomials ∏i Qi can vanish when two other quadratic polynomials vanish.
This video was produced by the International Centre for Physical Sciences, forming part of the Workshop on Algebraic Complexity Theory.
