Some lower bounds for the complexity of the linear programming feasibility problem over the reals

DOI10.1016/j.jco.2008.07.002zbMath1171.65045OpenAlexW1996324240MaRDI QIDQ998976

Bart Kuijpers, Rafael Grimson

Publication date: 30 January 2009

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2008.07.002

zbMATH Keywords

linear programmingalgebraic complexitycomplexity lower boundspolyhedra and polytopeslimiting hypersurface

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Complexity and performance of numerical algorithms (65Y20)

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
• Unnamed Item
• Factoring bivariate sparse (lacunary) polynomials
• The complexity of linear problems in fields
• Quantifier elimination: Optimal solution for two classical examples
• Solving systems of polynomial inequalities in subexponential time
• Real quantifier elimination is doubly exponential
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• On the intrinsic complexity of elimination theory
• The hardness of polynomial equation solving
• Lower bounds for arithmetic networks
• Linear optimization and extensions
• Semi-algebraic decision complexity, the real spectrum, and degree
• On the Theoretical and Practical Complexity of the Existential Theory of Reals
• The Computational Complexity of Continued Fractions
• The intrinsic complexity of parametric elimination methods
• Constraint Databases
• Algorithms in real algebraic geometry