Random sampling in computational algebra: Helly numbers and violator spaces

DOI10.1016/j.jsc.2016.01.001zbMath1357.68302arXiv1503.08804OpenAlexW2963123985MaRDI QIDQ277210

Despina Stasi, Jesús A. De Loera, Sonja Petrović

Publication date: 4 May 2016

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

randomized algorithmpolynomial systemsideal generatorslarge sparse systems of equationsviolator spaces

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Randomized algorithms (68W20) Solving polynomial systems; resultants (13P15)

Related Items

Random monomial ideals, Learning a performance metric of Buchberger's algorithm, Bounding Helly Numbers via Betti Numbers, Helly numbers of algebraic subsets of \(\mathbb{R}^{d}\) and an extension of Doignon's theorem, Helly’s theorem: New variations and applications

Uses Software

• Macaulay2
• PHCpack
• 4ti2
• Bertini
• GitHub
• Chordal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a problem posed by Steve Smale
• A proof of Hilbert's Nullstellensatz
• Computing generating sets of lattice ideals and Markov bases of lattices
• On Smale's 17th problem: a probabilistic positive solution
• Violator spaces: Structure and algorithms
• Helly-type theorems for varieties
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Helly-type theorems and generalized linear programming
• The minimal components of the Mayr-Meyer ideals.
• A Helly type theorem for hypersurfaces
• A subexponential bound for linear programming
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Graph-Coloring Ideals
• Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
• Sparse Gröbner bases
• The Structure of Polynomial Ideals and Gröbner Bases
• A Fast Monte-Carlo Test for Primality
• Las Vegas algorithms for linear and integer programming when the dimension is small
• Algorithm 795
• The Geometry of Syzygies
• A combinatorial bound for linear programming and related problems
• The Geometry of Multivariate Polynomial Division and Elimination
• Factoring Polynomials Over Large Finite Fields