On the number of zero-patterns of a sequence of polynomials

DOI10.1090/S0894-0347-01-00367-8zbMath0978.12001OpenAlexW1543186430MaRDI QIDQ2719034

László Babai, Murali Ganapathy, Lajos Rónyai

Publication date: 14 May 2001

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0894-0347-01-00367-8

zbMATH Keywords

polynomialsquantifier eliminationzero-pattern

Mathematics Subject Classification ID

Model-theoretic algebra (03C60) Polynomials in general fields (irreducibility, etc.) (12E05) Asymptotic enumeration (05A16)

Related Items (18)

Zero-patterns of polynomials and Newton polytopes. ⋮ Ramsey properties of algebraic graphs and hypergraphs ⋮ The (minimum) rank of typical fooling-set matrices ⋮ Counting dope matrices ⋮ Generic classification and asymptotic enumeration of dope matrices ⋮ Lower bounds for comparison based evolution strategies using VC-dimension and sign patterns ⋮ On the Number of Biased Graphs ⋮ On Linear Secret Sharing for Connectivity in Directed Graphs ⋮ On the construction of a family of transversal subspaces over finite fields ⋮ Two notions of unit distance graphs ⋮ Expected values of parameters associated with the minimum rank of a graph ⋮ On the asymptotic proportion of connected matroids ⋮ An asymptotically tight bound on the number of semi-algebraically connected components of realizable sign conditions ⋮ On graphs of minimum skew rank 4 ⋮ VC density of definable families over valued fields ⋮ The minrank of random graphs over arbitrary fields ⋮ Unnamed Item ⋮ On the hardness of approximating max-satisfy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for monotone span programs
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• A theorem on flows in networks
• Definability and fast quantifier elimination in algebraically closed fields
• Bounds for the degrees in the Nullstellensatz
• ``Integer-making theorems
• Intersection theorems with geometric consequences
• A combinatorial approach to complexity
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On t-designs
• Superpolynomial lower bounds for monotone span programs
• Topics in multiplicative number theory
• Combinatorial Properties of Matrices of Zeros and Ones
• Ramsey graphs cannot be defined by real polynomials
• On Two-Distance Sets in Euclidean Space
• Sharp Effective Nullstellensatz
• Repeated communication and Ramsey graphs
• On the number of cells defined by a family of polynomials on a variety
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the Betti Numbers of Real Varieties
• Some remarks on the theory of graphs
• A Note on Fisher's Inequality for Balanced Incomplete Block Designs

This page was built for publication: On the number of zero-patterns of a sequence of polynomials