Document Open Access Logo

Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials

Authors Shir Peleg , Amir Shpilka

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.43.pdf
  • Filesize: 0.7 MB
  • 15 pages

Document Identifiers

Author Details

Shir Peleg
  • Tel Aviv University, Israel
Amir Shpilka
  • Tel Aviv University, Israel

Funding

  • Peleg, Shir: The research leading to these results has received funding from the Israel Science Foundation (grant number 514/20) and from the Len Blavatnik and the Blavatnik Family foundation.
  • Shpilka, Amir: The research leading to these results has received funding from the Israel Science Foundation (grant number 514/20) and from the Len Blavatnik and the Blavatnik Family foundation.

Cite AsGet BibTex

Shir Peleg and Amir Shpilka. Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.43

Abstract

In this work we extend the robust version of the Sylvester-Gallai theorem, obtained by Barak, Dvir, Wigderson and Yehudayoff, and by Dvir, Saraf and Wigderson, to the case of quadratic polynomials. Specifically, we prove that if {𝒬} ⊂ ℂ[x₁.…,x_n] is a finite set, |{𝒬}| = m, of irreducible quadratic polynomials that satisfy the following condition There is δ > 0 such that for every Q ∈ {𝒬} there are at least δ m polynomials P ∈ {𝒬} such that whenever Q and P vanish then so does a third polynomial in {𝒬}⧵{Q,P}. then dim(span) = Poly(1/δ). The work of Barak et al. and Dvir et al. studied the case of linear polynomials and proved an upper bound of O(1/δ) on the dimension (in the first work an upper bound of O(1/δ²) was given, which was improved to O(1/δ) in the second work).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Mathematical analysis
  • Theory of computation → Computational geometry
Keywords
  • Sylvester-Gallai theorem
  • quadratic polynomials
  • Algebraic computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Manindra Agrawal. Proving lower bounds via pseudo-random generators. In Ramaswamy Ramanujam and Sandeep Sen, editors, FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, volume 3821 of Lecture Notes in Computer Science, pages 92-105. Springer, 2005. URL: https://doi.org/10.1007/11590156_6.
  2. Manindra Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 67-75. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.32.
  3. Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff. Fractional Sylvester-Gallai theorems. Proceedings of the National Academy of Sciences, 110(48):19213-19219, 2013. Google Scholar
  4. Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic independence and blackbox identity testing. Inf. Comput., 222:2-19, 2013. URL: https://doi.org/10.1016/j.ic.2012.10.004.
  5. Peter Borwein and William O. J. Moser. A survey of Sylvester’s problem and its generalizations. Aequationes Mathematicae, 40:111-135, 1990. URL: https://doi.org/doi:10.1007/BF02112289.
  6. Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Hardness vs Randomness for Bounded Depth Arithmetic Circuits. In Rocco A. Servedio, editor, 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pages 13:1-13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.CCC.2018.13.
  7. Zeev Dvir. Incidence theorems and their applications. Found. Trends Theor. Comput. Sci., 6(4):257-393, 2012. URL: https://doi.org/10.1561/0400000056.
  8. Zeev Dvir and Guangda Hu. Sylvester-Gallai for Arrangements of Subspaces. Discrete & Computational Geometry, 56(4):940-965, 2016. URL: https://doi.org/10.1007/s00454-016-9781-7.
  9. Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Improved rank bounds for design matrices and a new proof of kelly’s theorem. Forum of Mathematics, Sigma, 2, 2014. URL: http://arxiv.org/abs/1211.0330.
  10. Zeev Dvir and Amir Shpilka. Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput., 36(5):1404-1434, 2007. URL: https://doi.org/10.1137/05063605X.
  11. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279-1293, 2009. URL: https://doi.org/10.1137/080735850.
  12. Paul Erdös. Problems for Solution: 4065. The American Mathematical Monthly, 50(1):65, 1943. URL: http://www.jstor.org/stable/2304011.
  13. Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. A deterministic parallel algorithm for bipartite perfect matching. Commun. ACM, 62(3):109-115, 2019. URL: https://doi.org/10.1145/3306208.
  14. Michael A. Forbes. Polynomial identity testing of read-once oblivious algebraic branching programs. PhD thesis, Massachusetts Institute of Technology, 2014. Google Scholar
  15. Michael A. Forbes and Amir Shpilka. Explicit noether normalization for simultaneous conjugation via polynomial identity testing. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 527-542. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_37.
  16. Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits. Theory of Computing, 14(1):1-45, 2018. URL: https://doi.org/10.4086/toc.2018.v014a018.
  17. Tibor Gallai. Solution to Problem 4065. The American Mathematical Monthly, 51:169-171, 1944. Google Scholar
  18. Abhibhav Garg, Rafael Oliviera, and Akash Kumar Sengupta. Robust Radical Sylvester-Gallai Theorem for Quadratics. Personal communication, 2021. Google Scholar
  19. Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, and Shubhangi Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR, abs/1701.01717, 2017. URL: http://arxiv.org/abs/1701.01717.
  20. Ankit Gupta. Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties. Electronic Colloquium on Computational Complexity (ECCC), 21:130, 2014. URL: http://eccc.hpi-web.de/report/2014/130.
  21. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064-1079, 2016. URL: https://doi.org/10.1137/140957123.
  22. Sten Hansen. A generalization of a theorem of Sylvester on the lines determined by a finite point set. Mathematica Scandinavica, 16:175-180, 1965. Google Scholar
  23. Joos Heintz and Claus-Peter Schnorr. Testing polynomials which are easy to compute (extended abstract). In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 262-272. ACM, 1980. URL: https://doi.org/10.1145/800141.804674.
  24. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. URL: https://doi.org/10.1007/s00037-004-0182-6.
  25. Zohar S. Karnin and Amir Shpilka. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 274-285. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/CCC.2009.18.
  26. Neeraj Kayal and Shubhangi Saraf. Blackbox polynomial identity testing for depth 3 circuits. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 198-207. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/FOCS.2009.67.
  27. Leroy Milton Kelly. A resolution of the Sylvester-Gallai problem of J.-P. Serre. Discrete & Computational Geometry, 1(2):101-104, 1986. Google Scholar
  28. Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of polynomial identity testing and polynomial factorization. Computational Complexity, 24(2):295-331, 2015. URL: https://doi.org/10.1007/s00037-015-0102-y.
  29. Mrinal Kumar and Ramprasad Saptharishi. Hardness-Randomness Tradeoffs for Algebraic Computation. Bull. EATCS, 129, 2019. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/591/599.
  30. Eberhard Melchior. Über Vielseite der Projektive Ebene. Deutsche Mathematik, 5:461-475, 1941. Google Scholar
  31. Ketan D. Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. J. Amer. Math. Soc., 30(1):225-309, 2017. Google Scholar
  32. Shir Peleg and Amir Shpilka. A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials. In Shubhangi Saraf, editor, 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs, pages 8:1-8:33. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.8.
  33. Shir Peleg and Amir Shpilka. Polynomial time deterministic identity testingalgorithm for Σ^[3]ΠΣΠ^[2] circuits via edelstein-kelly type theorem for quadratic polynomials. CoRR, abs/2006.08263, 2020. URL: http://arxiv.org/abs/2006.08263.
  34. Nitin Saxena. Progress on polynomial identity testing. Bulletin of EATCS, 99:49-79, 2009. URL: https://eccc.weizmann.ac.il/report/2009/101/.
  35. Nitin Saxena. Progress on polynomial identity testing-ii. In M. Agrawal and V. Arvind, editors, Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, Progress in Computer Science and Applied Logic, pages 131-146. Springer International Publishing, 2014. URL: https://books.google.co.il/books?id=U7ApBAAAQBAJ.
  36. Nitin Saxena and Comandur Seshadhri. Blackbox identity testing for bounded top-fanin depth-3 circuits: The field doesn't matter. SIAM J. Comput., 41(5):1285-1298, 2012. URL: https://doi.org/10.1137/10848232.
  37. Nitin Saxena and Comandur Seshadhri. From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM, 60(5):33, 2013. URL: https://doi.org/10.1145/2528403.
  38. Jean-Pierre Serre. Advanced Problems: 5359. The American Mathematical Monthly, 73(1):89, 1966. URL: http://www.jstor.org/stable/2313941.
  39. Amir Shpilka. Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J. Comput., 38(6):2130-2161, 2009. URL: https://doi.org/10.1137/070694879.
  40. Amir Shpilka. Sylvester-Gallai type theorems for quadratic polynomials. Discrete Analysis, 13, 2020. Google Scholar
  41. Amir Shpilka and Amir Yehudayoff. Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. URL: https://doi.org/10.1561/0400000039.
  42. Gaurav Sinha. Reconstruction of Real Depth-3 Circuits with Top Fan-In 2. In Ran Raz, editor, 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume 50 of LIPIcs, pages 31:1-31:53. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.31.
  43. Ola Svensson and Jakub Tarnawski. The Matching Problem in General Graphs Is in Quasi-NC. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 696-707. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.70.
  44. James Joseph Sylvester. Mathematical question 11851. Educational Times, pages 59-98, 1893. Google Scholar
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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact