Sylvester-Gallai type theorems for quadratic polynomials

DOI10.19086/da.14492zbMath1456.68039arXiv1904.06245OpenAlexW3163994581MaRDI QIDQ5126776

Amir Shpilka

Publication date: 20 October 2020

Published in: discrete Analysis, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.06245

zbMATH Keywords

combinatoricsquadratic polynomialsarithmetic circuitspolynomial identity testingSylvester-Gallai theorem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Erd?s problems and related topics of discrete geometry (52C10) Randomized algorithms (68W20) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items

On a conjecture of Kelly on (1, 3)-representation of Sylvester-Gallai designs, A generalized Sylvester–Gallai-type theorem for quadratic polynomials, Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs, Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs, A generalized sylvester-gallai type theorem for quadratic polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Sylvester-Gallai for arrangements of subspaces
• Black-box identity testing of depth-4 multilinear circuits
• Equivalence of polynomial identity testing and polynomial factorization
• A survey of Sylvester's problem and its generalizations
• Geometric complexity theory V: Efficient algorithms for Noether normalization
• Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
• IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
• Algebraic Independence and Blackbox Identity Testing
• Arithmetic Circuits: A survey of recent results and open questions
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
• Progress on Polynomial Identity Testing - II
• Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter
• Linear matroid intersection is in quasi-NC
• Fractional Sylvester–Gallai theorems
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Bipartite perfect matching is in quasi-NC
• From sylvester-gallai configurations to rank bounds
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Probability and Computing
• Bisecants of Finite Collections of Sets in Linear Spaces
• A Generalization of a Theorem of Sylvester on the Lines Determined by a Finite Point Set.
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds