research-article

Sylvester-Gallai type theorems for quadratic polynomials

Author:

Amir ShpilkaAuthors Info & Claims

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

Pages 1203 - 1214

https://doi.org/10.1145/3313276.3316341

Published: 23 June 2019 Publication History

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 Q₁,Q₂∈ Q there is a third polynomial Q₃∈Q so that whenever Q₁ and Q₂ vanish then also Q₃ 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).

References

[1]

{Agr05} 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.

Digital Library

[2]

{BM90} Peter Borwein and William O. J. Moser. A survey of Sylvester’s problem and its generalizations. Aequationes Mathematicae, 40:111–135, 1990.

[3]

{BMS13} Malte Beecken, Johannes Mittmann, and Nitin Saxena. Algebraic independence and blackbox identity testing. Inf. Comput., 222:2–19, 2013.

Digital Library

[4]

{CKS18} 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 fuer Informatik, 2018.

Digital Library

[5]

{CLO07} 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.

Digital Library

[6]

{DH16} Zeev Dvir and Guangda Hu. Sylvester-Gallai for Arrangements of Subspaces. Discrete & Computational Geometry, 56(4):940–965, 2016.

Digital Library

[7]

{DS07} 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.

Digital Library

[8]

{DSW14} 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. Pre-print available at arXiv:1211.0330.

[9]

{DSY09} Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. SIAM J. Comput., 39(4):1279–1293, 2009.

Digital Library

[10]

{EK66} Michael Edelstein and Leroy M. Kelly. Bisecants of finite collections of sets in linear spaces. Canadanian Journal of Mathematics, 18:375–280, 1966.

[11]

{FGT16} Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 754–763. ACM, 2016.

Digital Library

[12]

{For14} Michael A. Forbes. Polynomial identity testing of read-once oblivious algebraic branching programs. PhD thesis, Massachusetts Institute of Technology, 2014.

[13]

{FS13} 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.

[14]

{FSV17} Michael A. Forbes, Amir Shpilka, and Ben Lee Volk. Succinct hitting sets and barriers to proving algebraic circuits lower bounds. In Hatami et al. { HMK17 }, pages 653–664.

[15]

{FV11} Lance Fortnow and Salil P. Vadhan, editors. Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011. ACM, 2011.

[16]

{GT17} Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in quasi-NC. In Hatami et al. { HMK17 }, pages 821–830. {Gup14} Ankit Gupta. Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties. Electronic Colloquium on Computational Complexity (ECCC), 21:130, 2014.

[17]

{Han65} Sten Hansen. A generalization of a theorem of Sylvester on the lines determined by a finite point set. Mathematica Scandinavica, 16:175–180, 1965.

[18]

{HMK17} 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. ACM, 2017.

[19]

{HS80} Joos Heintz and Claus-Peter Schnorr. Testing Polynomials which Are Easy to Compute (Extended Abstract). In Proceedings of the 12th annual STOC, pages 262–272, 1980.

Digital Library

[20]

{KI04} Valentine Kabanets and Russell Impagliazzo. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity, 13(1-2):1–46, 2004.

Digital Library

[21]

{KS09a} Zohar Shay 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.

Digital Library

[22]

{KS09b} 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.

Digital Library

[23]

{KSS15} Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka. Equivalence of Polynomial Identity Testing and Polynomial Factorization. Computational Complexity, 24(2):295–331, 2015.

Digital Library

[24]

{MU05} Michael Mitzenmacher and Eli Upfal. Probability and Computing – Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.

Digital Library

[25]

{Mul17} Ketan D. Mulmuley. Geometric complexity theory V: Efficient algorithms for Noether normalization. J. Amer. Math. Soc., 30(1):225–309, 2017.

[26]

{Pel19} Shir Peleg. Sylvester-Gallai type theorem for quadratic polynomials. Master’s thesis, Tel Aviv University, 2019.

[27]

{Sax09} Nitin Saxena. Progress on polynomial identity testing. Bulletin of EATCS, 99:49–79, 2009.

[28]

{Sax14} 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.

[29]

{Shp09} Amir Shpilka. Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. SIAM J. Comput., 38(6):2130–2161, 2009.

Digital Library

[30]

{Sin16} 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.

Digital Library

[31]

{SS12} Nitin Saxena and C. Seshadhri. Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn’t Matter. SIAM J. Comput., 41(5):1285–1298, 2012.

[32]

{SS13} Nitin Saxena and C. Seshadhri. From Sylvester-Gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM, 60(5):33, 2013.

Digital Library

[33]

{ST17} 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.

[34]

{SV11} Shubhangi Saraf and Ilya Volkovich. Black-box identity testing of depth-4 multilinear circuits. In Fortnow and Vadhan { FV11 }, pages 421–430.

[35]

{SY10} 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.

Digital Library

Cited By

Saha CThankey B(2024)Hitting Sets for Orbits of Circuit Classes and Polynomial FamiliesACM Transactions on Computation Theory10.1145/366580016:3(1-50)Online publication date: 23-May-2024
https://dl.acm.org/doi/10.1145/3665800
Guo Z(2024)Variety Evasive Subspace Familiescomputational complexity10.1007/s00037-024-00256-133:2Online publication date: 16-Jul-2024
https://doi.org/10.1007/s00037-024-00256-1
Andrews RForbes MLeonardi SGupta A(2022)Ideals, determinants, and straightening: proving and using lower bounds for polynomial idealsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520025(389-402)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520025
Show More Cited By

Index Terms

Sylvester-Gallai type theorems for quadratic polynomials
1. Theory of computation
  1. Computational complexity and cryptography
    1. Algebraic complexity theory
  2. Randomness, geometry and discrete structures

Recommendations

Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation

Polynomial Identity Testing (PIT) algorithms have focussed on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are the ...
A generalized sylvester-gallai type theorem for quadratic polynomials
CCC '20: Proceedings of the 35th Computational Complexity Conference

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 [MATH HERE] circuits. Specifically, we prove that if a ...
Subexponential size hitting sets for bounded depth multilinear formulas
CCC '15: Proceedings of the 30th Conference on Computational Complexity

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

For depth-3 multilinear formulas, of size ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

June 2019

1258 pages

ISBN:9781450367059

DOI:10.1145/3313276

General Chair:
Moses Charikar
Stanford University
,
Program Chair:
Edith Cohen
Google, USA / Tel Aviv University, Israel

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '19

Sponsor:

SIGACT

STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing

June 23 - 26, 2019

AZ, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
120
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Saha CThankey B(2024)Hitting Sets for Orbits of Circuit Classes and Polynomial FamiliesACM Transactions on Computation Theory10.1145/366580016:3(1-50)Online publication date: 23-May-2024
https://dl.acm.org/doi/10.1145/3665800
Guo Z(2024)Variety Evasive Subspace Familiescomputational complexity10.1007/s00037-024-00256-133:2Online publication date: 16-Jul-2024
https://doi.org/10.1007/s00037-024-00256-1
Andrews RForbes MLeonardi SGupta A(2022)Ideals, determinants, and straightening: proving and using lower bounds for polynomial idealsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520025(389-402)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520025
Oliveira RSengupta A(2022)Radical Sylvester-Gallai Theorem for Cubics2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00027(212-220)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00027
Kumar CSingh A(2022)On a conjecture of Kelly on (1, 3)-representation of Sylvester–Gallai designsProceedings - Mathematical Sciences10.1007/s12044-022-00656-9132:1Online publication date: 20-Apr-2022
https://doi.org/10.1007/s12044-022-00656-9
Guo Z(2021)Variety evasive subspace familiesProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.20Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.20
Dutta PDwivedi PSaxena N(2021)Deterministic identity testing paradigms for bounded top-fanin depth-4 circuitsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.11Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.11
Peleg SShpilka AKhuller SVassilevska Williams V(2021)Polynomial time deterministic identity testing algorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein–Kelly type theorem for quadratic polynomialsProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451013(259-271)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451013
Peleg SShpilka AAceto L(2020)A generalized sylvester-gallai type theorem for quadratic polynomialsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.8(1-33)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.8

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten