On the combinatorial and algebraic complexity of quantifier elimination
From MaRDI portal
Publication:4371694
DOI10.1145/235809.235813zbMath0885.68070OpenAlexW2151549243WikidataQ57253831 ScholiaQ57253831MaRDI QIDQ4371694
Saugata Basu, Richard Pollack, Marie-Françoise Roy
Publication date: 22 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1996-43/
Related Items
Towards faster real algebraic numbers, The theory of Liouville functions, The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements, Parameterized Analysis of Art Gallery and Terrain Guarding, Parametric toricity of steady state varieties of reaction networks, An introduction to multiscale techniques in the theory of Anderson localization. I, Semidefinite Approximations of Projections and Polynomial Images of SemiAlgebraic Sets, Discrete semantics for hybrid automata. Avoiding misleading assumptions in systems biology, Guarding galleries and terrains, Real quantifier elimination for the synthesis of optimal numerical algorithms (case study: square root computation), On the planar piecewise quadratic 1-center problem, A logic and computation for Popper's conditional probabilities, A potential reduction algorithm for two-person zero-sum mean payoff stochastic games, Polynomial-time approximation schemes for circle and other packing problems, Generalized polar varieties: geometry and algorithms, Polar varieties, real equation solving, and data structures: the hypersurface case, On computing a set of points meeting every cell defined by a family of polynomials on a variety, A polynomial-time algorithm for computing low CP-rank decompositions, Symbolic computation in hyperbolic programming, Topological types of Pfaffian manifolds, Logic for physical space. From antiquity to present day, On the complexity of quantified linear systems, Computing the average inter-sample time of event-triggered control using quantitative automata, Unnamed Item, VerifyRealRoots: a Matlab package for computing verified real solutions of polynomials systems of equations and inequalities, Faster real root decision algorithm for symmetric polynomials, Refined bounds on the number of connected components of sign conditions on a variety, Sphere and dot product representations of graphs, Anderson localization for Jacobi matrices associated with high-dimensional skew shifts, Conic optimization-based algorithms for nonnegative matrix factorization, An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem, Variant quantifier elimination, Approximating the Rectilinear Crossing Number, The parameterized complexity of guarding almost convex polygons, A survey of some methods for real quantifier elimination, decision, and satisfiability and their applications, Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces, Numerically computing real points on algebraic sets, Open weak CAD and its applications, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, Homogeneous multivariate polynomials with the half-plane property, Quantum automata and algebraic groups, Computing the first few Betti numbers of semi-algebraic sets in single exponential time, The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete., Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials, Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time, Computing the first Betti number of a semi-algebraic set, A complexity perspective on entailment of parameterized linear constraints, Topological complexity of the range searching, A hierarchy of proof rules for checking positive invariance of algebraic and semi-algebraic sets, A search-based procedure for nonlinear real arithmetic, Finding at least one point in each connected component of a real algebraic set defined by a single equation, Intrinsic complexity estimates in polynomial optimization, A survey of computational complexity results in systems and control, Elementary recursive quantifier elimination based on Thom encoding and sign determination, An improved semidefinite programming hierarchy for testing entanglement, On projections of semi-algebraic sets defined by few quadratic inequalities, Centerpoints: A Link between Optimization and Convex Geometry, A DECISION PROCEDURE FOR PROBABILITY CALCULUS WITH APPLICATIONS, Quasi-interpretations. A way to control resources, An Almost Optimal Algorithm for Computing Nonnegative Rank, Supporting Global Numerical Optimization of Rational Functions by Generic Symbolic Convexity Tests, On sign conditions over real multivariate polynomials, The continuous Skolem-Pisot problem, Back-and-forth systems for generic curves and a decision algorithm for the limit theory, The set of realizations of a max-plus linear sequence is semi-polyhedral, Complexity of cylindrical decompositions of sub-Pfaffian, On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting, Elimination of quantifiers and undecidability in spatial logics for concurrency, Inclusion dynamics hybrid automata, Truth table invariant cylindrical algebraic decomposition, Realizing RCC8 networks using convex regions, Computing the homology of semialgebraic sets. I: Lax formulas, Computing roadmaps of semi-algebraic sets on a variety, Definability of Geometric Properties in Algebraically Closed Fields, Simultaneous elimination by using several tools from real algebraic geometry, Computing a Nonnegative Matrix Factorization---Provably, On the Generation of Positivstellensatz Witnesses in Degenerate Cases, Sign determination in residue number systems, Unnamed Item, Parts of quantum states, Exact Algorithms for Linear Matrix Inequalities, Anderson localization for a generalized Maryland model with potentials given by skew shifts, Techniques and results on approximation algorithms for packing circles, Approximating the rectilinear crossing number, Anderson localization for long-range operators with singular potentials, Euclidean distance degree and mixed volume, Anderson localization for multi-frequency quasi-periodic Jacobi operators, Some speed-ups and speed limits for real algebraic geometry, Special algorithm for stability analysis of multistable biological regulatory systems, Cooperating techniques for solving nonlinear real arithmetic in the \texttt{cvc5} SMT solver (system description), Real computations with fake numbers, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity, Transfer theorems via sign conditions, Real solving for positive dimensional systems., Systems of rational polynomial equations have polynomial size approximate zeros on the average, Anderson localization for Schrödinger operators on \(\mathbb{Z}^2\)with quasi-periodic potential
