On the combinatorial and algebraic complexity of quantifier elimination
From MaRDI portal
Recommendations
- On the Complexity of Quantifier Elimination: the Structural Approach
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- scientific article; zbMATH DE number 3895043
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
- scientific article; zbMATH DE number 3845566
- The quantifier complexity of NF
- Complexity bounds in elimination theory -- a survey.
- scientific article; zbMATH DE number 4075030
Cited in
(only showing first 100 items - show all)- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
- Sign determination in residue number systems
- An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
- 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
- Homogeneous multivariate polynomials with the half-plane property
- On the number of sets definable by polynomials
- Some speed-ups and speed limits for real algebraic geometry
- Real computations with fake numbers
- Transfer theorems via sign conditions
- Anderson localization for Schrödinger operators on \(\mathbb{Z}^2\)with quasi-periodic potential
- A survey of some methods for real quantifier elimination, decision, and satisfiability and their applications
- Open weak CAD and its applications
- Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
- Simultaneous elimination by using several tools from real algebraic geometry
- Real solving for positive dimensional systems.
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Towards faster real algebraic numbers
- Numerically computing real points on algebraic sets
- The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete.
- Topological complexity of the range searching
- Anderson localization for a generalized Maryland model with potentials given by skew shifts
- Techniques and results on approximation algorithms for packing circles
- Euclidean distance degree and mixed volume
- Anderson localization for multi-frequency quasi-periodic Jacobi operators
- Cooperating techniques for solving nonlinear real arithmetic in the \texttt{cvc5} SMT solver (system description)
- An introduction to multiscale techniques in the theory of Anderson localization. I
- A logic and computation for Popper's conditional probabilities
- Anderson localization for Jacobi matrices associated with high-dimensional skew shifts
- Intrinsic complexity estimates in polynomial optimization
- Computing the homology of semialgebraic sets. I: Lax formulas
- Approximating the rectilinear crossing number
- Special algorithm for stability analysis of multistable biological regulatory systems
- On the planar piecewise quadratic 1-center problem
- Generalized polar varieties: geometry and algorithms
- Quantum automata and algebraic groups
- Computing the first few Betti numbers of semi-algebraic sets in single exponential time
- On projections of semi-algebraic sets defined by few quadratic inequalities
- 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
- Realizing RCC8 networks using convex regions
- Real quantifier elimination for the synthesis of optimal numerical algorithms (case study: square root computation)
- A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
- Computing the average inter-sample time of event-triggered control using quantitative automata
- Computing a nonnegative matrix factorization -- provably
- Exact algorithms for linear matrix inequalities
- Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
- Approximating the rectilinear crossing number
- Quantifier elimination over finite fields using Gröbner bases
- scientific article; zbMATH DE number 4014674 (Why is no real title available?)
- On the Generation of Positivstellensatz Witnesses in Degenerate Cases
- Parts of quantum states
- Improved Algorithms for Sign Determination and Existential Quantifier Elimination
- New results on quantifier elimination over real closed fields and applications to constraint databases
- The theory of Liouville functions
- The computational complexity of trembling hand perfection and other equilibrium refinements
- Polynomial-time approximation schemes for circle and other packing problems
- On the complexity of identifying head-elementary-set-free programs
- A polynomial-time algorithm for computing low CP-rank decompositions
- Semidefinite approximations of projections and polynomial images of semialgebraic sets
- scientific article; zbMATH DE number 4150340 (Why is no real title available?)
- A decision procedure for probability calculus with applications
- Supporting global numerical optimization of rational functions by generic symbolic convexity tests
- scientific article; zbMATH DE number 4008374 (Why is no real title available?)
- Logic for physical space. From antiquity to present day
- On the complexity of quantified linear systems
- Refined bounds on the number of connected components of sign conditions on a variety
- Sphere and dot product representations of graphs
- Variant quantifier elimination
- scientific article; zbMATH DE number 1253963 (Why is no real title available?)
- scientific article; zbMATH DE number 589121 (Why is no real title available?)
- Algorithms of intrinsic complexity for point searching in compact real singular hypersurfaces
- scientific article; zbMATH DE number 1490034 (Why is no real title available?)
- Symbolic computation in hyperbolic programming
- Computing roadmaps of semi-algebraic sets on a variety
- Definability of Geometric Properties in Algebraically Closed Fields
- Quantifier elimination for a class of exponential polynomial formulas
- Topological types of Pfaffian manifolds
- A complexity perspective on entailment of parameterized linear constraints
- Matrix completion and related problems via strong duality
- Parameterized Analysis of Art Gallery and Terrain Guarding
- An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
- A search-based procedure for nonlinear real arithmetic
- Elementary recursive quantifier elimination based on Thom encoding and sign determination
- Computer Science Logic
- An improved semidefinite programming hierarchy for testing entanglement
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- Generalized polar varieties and an efficient real elimination.
- Quasi-interpretations. A way to control resources
- Advances in Databases and Information Systems
- Centerpoints: a link between optimization and convex geometry
- An almost optimal algorithm for computing nonnegative rank
- Anderson localization for long-range operators with singular potentials
- Finding at least one point in each connected component of a real algebraic set defined by a single equation
- A survey of computational complexity results in systems and control
- Back-and-forth systems for generic curves and a decision algorithm for the limit theory
- Complexity of cylindrical decompositions of sub-Pfaffian
- Truth table invariant cylindrical algebraic decomposition
- VerifyRealRoots: a Matlab package for computing verified real solutions of polynomials systems of equations and inequalities
- Faster real root decision algorithm for symmetric polynomials
This page was built for publication: On the combinatorial and algebraic complexity of quantifier elimination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4371694)
