A Polyhedral Characterization of Border Bases
From MaRDI portal
Publication:5744696
DOI10.1137/140977990zbMath1332.13021arXiv0912.1502MaRDI QIDQ5744696
Gábor Braun, Sebastian Pokutta
Publication date: 19 February 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0912.1502
65H10: Numerical computation of solutions to systems of equations
68R05: Combinatorics in computer science
90C27: Combinatorial optimization
13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
14Q15: Computational aspects of higher-dimensional varieties
Related Items
Computing an Invariant of a Linear Code, Computing all border bases for ideals of points, A Polyhedral Characterization of Border Bases, On the weak order ideal associated to linear codes, Complexity of Gröbner basis detection and border basis detection, Computing border bases without using a term ordering, Computing coupled border bases
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
- Approximate computation of zero-dimensional polynomial ideals
- SCIP: solving constraint integer programs
- Computing border bases
- Deformations of border bases
- Border basis relaxation for polynomial optimization
- Stable border bases for ideals of points
- On border basis and Gröbner basis schemes
- Complexity of Gröbner basis detection and border basis detection
- Characterizations of border bases
- The polynomial method and restricted sums of congruence classes
- Computing border bases without using a term ordering
- Recognizing graph theoretic properties with polynomial ideals
- Stable normal forms for polynomial system solving
- Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization
- Inapproximability of Combinatorial Problems via Small LPs and SDPs
- Subideal border bases
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
- An Application of Möller’s Algorithm to Coding Theory
- Maximal Closure of a Graph and Applications to Combinatorial Problems
- Combinatorial Nullstellensatz
- An Introduction to Statistical Learning
- Algebraic Attacks Galore!
- Border basis detection is NP-complete
- Generalized normal forms and polynomial system solving
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Linear vs. semidefinite extended formulations
- A Polyhedral Characterization of Border Bases
- Extended formulations in combinatorial optimization
- Cutting corners
