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

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