Document Open Access Logo

A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials

Authors Shir Peleg, Amir Shpilka

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.8.pdf
  • Filesize: 0.66 MB
  • 33 pages

Document Identifiers

Author Details

Shir Peleg
  • Department of Computer Science, Tel Aviv University, Israel
Amir Shpilka
  • Department of Computer Science, Tel Aviv University, Israel

Funding

The research leading to these results has received funding from the Israel Science Foundation (grant number 552/16) and from the Len Blavatnik and the Blavatnik Family foundation.
  • Shpilka, Amir: Part of this work was done while the author was a visiting professor at NYU.

Cite As Get BibTex

Shir Peleg and Amir Shpilka. A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 8:1-8:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.8

Abstract

In this work we prove a version of the Sylvester-Gallai theorem for quadratic polynomials that takes us one step closer to obtaining a deterministic polynomial time algorithm for testing zeroness of Σ^{[3]}ΠΣΠ^{[2]} circuits. Specifically, we prove that if a finite set of irreducible quadratic polynomials 𝒬 satisfy that for every two polynomials Q₁,Q₂ ∈ 𝒬 there is a subset 𝒦 ⊂ 𝒬, such that Q₁,Q₂ ∉ 𝒦 and whenever Q₁ and Q₂ vanish then ∏_{Q_i∈𝒦} Q_i vanishes, then the linear span of the polynomials in 𝒬 has dimension O(1). This extends the earlier result [Amir Shpilka, 2019] that showed a similar conclusion when |𝒦| = 1. 
An important technical step in our proof is a theorem classifying all the possible cases in which a product of quadratic polynomials can vanish when two other quadratic polynomials vanish. I.e., when the product is in the radical of the ideal generated by the two quadratics. This step extends a result from [Amir Shpilka, 2019] that studied the case when one quadratic polynomial is in the radical of two other quadratics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Algebraic computation
  • Computational complexity
  • Computational geometry

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. Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, and Amir Shpilka. Tight lower bounds for linear 2-query lccs over finite fields. Combinatorica, 36(1):1-36, 2016. URL: https://doi.org/10.1007/s00493-015-3024-z.
  6. 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/10.1007/BF02112289.
  7. 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.
  8. David A. Cox, John Little, and Donal O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, 3rd edition, 2007. Google Scholar
  9. Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. Improved rank bounds for design matrices and a new proof of kelly’s theorem. CoRR, abs/1211.0330, 2012. 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. Michael Edelstein and Leroy M. Kelly. Bisecants of finite collections of sets in linear spaces. Canadian Journal of Mathematics, 18:375-280, 1966. Google Scholar
  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. 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.
  18. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 578-587, 2013. URL: https://doi.org/10.1109/FOCS.2013.68.
  19. Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in quasi-nc. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 821-830. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055440.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. Ketan D. Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. J. Amer. Math. Soc., 30(1):225-309, 2017. Google Scholar
  26. Shir Peleg and Amir Shpilka. A generalized sylvester-gallai type theorem for quadratic polynomials. CoRR, abs/2003.05152, 2020. URL: http://arxiv.org/abs/2003.05152.
  27. Shubhangi Saraf and Ilya Volkovich. Black-box identity testing of depth-4 multilinear circuits. Combinatorica, 38(5):1205-1238, 2018. URL: https://doi.org/10.1007/s00493-016-3460-4.
  28. Nitin Saxena. Progress on polynomial identity testing. Bulletin of EATCS, 99:49-79, 2009. URL: https://eccc.weizmann.ac.il/report/2009/101/.
  29. 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.
  30. 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.
  31. 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.
  32. 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.
  33. Amir Shpilka. Sylvester-gallai type theorems for quadratic polynomials. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 1203-1214. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316341.
  34. 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.
  35. 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.
  36. 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.
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 About DROPS Imprint Privacy Contact