Search Results

Documents authored by Garg, Abhibhav

Document
DOI: 10.4230/LIPIcs.SoCG.2025.52
Uniform Bounds on Product Sylvester-Gallai Configurations

Authors: Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let 𝕂 be an algebraically closed field of characteristic zero, and let ℱ = {F_1, …, F_m} ⊂ 𝕂[x_1, …, x_N] denote a collection of irreducible homogeneous polynomials of degree at most d, where each F_i is not a scalar multiple of any other F_j for i ≠ j. We define ℱ to be a product Sylvester-Gallai configuration if, for any two distinct polynomials F_i, F_j ∈ ℱ, the following condition is satisfied: ∏_{k≠i, j} F_k ∈ rad (F_i, F_j) . We prove that product Sylvester-Gallai configurations are inherently low dimensional. Specifically, we show that there exists a function λ : ℕ → ℕ, independent of 𝕂, N, and m, such that any product Sylvester-Gallai configuration must satisfy: dim(span_𝕂(ℱ)) ≤ λ(d). This result generalizes the main theorems from (Shpilka 2019, Peleg and Shpilka 2020, Oliveira and Sengupta 2023), and gets us one step closer to a full derandomization of the polynomial identity testing problem for the class of depth 4 circuits with bounded top and bottom fan-in.
Cite as

Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta. Uniform Bounds on Product Sylvester-Gallai Configurations. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.SoCG.2025.52,
  author =	{Garg, Abhibhav and Oliveira, Rafael and Sengupta, Akash Kumar},
  title =	{{Uniform Bounds on Product Sylvester-Gallai Configurations}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.52},
  URN =		{urn:nbn:de:0030-drops-232043},
  doi =		{10.4230/LIPIcs.SoCG.2025.52},
  annote =	{Keywords: Sylvester-Gallai theorem, arrangements of hypersurfaces, algebraic complexity, polynomial identity testing, algebraic geometry, commutative algebra}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.20
Radical Sylvester-Gallai Theorem for Tuples of Quadratics

Authors: Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
We prove a higher codimensional radical Sylvester-Gallai type theorem for quadratic polynomials, simultaneously generalizing [Hansen, 1965; Shpilka, 2020]. Hansen’s theorem is a high-dimensional version of the classical Sylvester-Gallai theorem in which the incidence condition is given by high-dimensional flats instead of lines. We generalize Hansen’s theorem to the setting of quadratic forms in a polynomial ring, where the incidence condition is given by radical membership in a high-codimensional ideal. Our main theorem is also a generalization of the quadratic Sylvester-Gallai Theorem of [Shpilka, 2020]. Our work is the first to prove a radical Sylvester-Gallai type theorem for arbitrary codimension k ≥ 2, whereas previous works [Shpilka, 2020; Shir Peleg and Amir Shpilka, 2020; Shir Peleg and Amir Shpilka, 2021; Garg et al., 2022] considered the case of codimension 2 ideals. Our techniques combine algebraic geometric and combinatorial arguments. A key ingredient is a structural result for ideals generated by a constant number of quadratics, showing that such ideals must be radical whenever the quadratic forms are far apart. Using the wide algebras defined in [Garg et al., 2022], combined with results about integral ring extensions and dimension theory, we develop new techniques for studying such ideals generated by quadratic forms. One advantage of our approach is that it does not need the finer classification theorems for codimension 2 complete intersection of quadratics proved in [Shpilka, 2020; Garg et al., 2022].
Cite as

Abhibhav Garg, Rafael Oliveira, Shir Peleg, and Akash Kumar Sengupta. Radical Sylvester-Gallai Theorem for Tuples of Quadratics. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 20:1-20:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.CCC.2023.20,
  author =	{Garg, Abhibhav and Oliveira, Rafael and Peleg, Shir and Sengupta, Akash Kumar},
  title =	{{Radical Sylvester-Gallai Theorem for Tuples of Quadratics}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{20:1--20:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.20},
  URN =		{urn:nbn:de:0030-drops-182903},
  doi =		{10.4230/LIPIcs.CCC.2023.20},
  annote =	{Keywords: Sylvester-Gallai theorem, arrangements of hypersurfaces, algebraic complexity, polynomial identity testing, algebraic geometry, commutative algebra}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.42
Robust Radical Sylvester-Gallai Theorem for Quadratics

Authors: Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials. More precisely, given a parameter 0 < δ ≤ 1 and a finite collection ℱ of irreducible and pairwise independent polynomials of degree at most 2, we say that ℱ is a (δ, 2)-radical Sylvester-Gallai configuration if for any polynomial F_i ∈ ℱ, there exist δ(|ℱ|-1) polynomials F_j such that |rad (F_i, F_j) ∩ ℱ| ≥ 3, that is, the radical of F_i, F_j contains a third polynomial in the set. We prove that any (δ, 2)-radical Sylvester-Gallai configuration ℱ must be of low dimension: that is dim span_ℂ{ℱ} = poly(1/δ).
Cite as

Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta. Robust Radical Sylvester-Gallai Theorem for Quadratics. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 42:1-42:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.SoCG.2022.42,
  author =	{Garg, Abhibhav and Oliveira, Rafael and Sengupta, Akash Kumar},
  title =	{{Robust Radical Sylvester-Gallai Theorem for Quadratics}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{42:1--42:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.42},
  URN =		{urn:nbn:de:0030-drops-160505},
  doi =		{10.4230/LIPIcs.SoCG.2022.42},
  annote =	{Keywords: Sylvester-Gallai theorem, arrangements of hypersurfaces, locally correctable codes, algebraic complexity, polynomial identity testing, algebraic geometry, commutative algebra}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact