Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets

DOI10.1090/CONM/697/14046zbMATH Open1390.14175arXiv1608.06828OpenAlexW2508521651MaRDI QIDQ4635358FDOQ4635358

Saugata Basu, Cordian Riener

Publication date: 16 April 2018

Published in: Ordered Algebraic Structures and Related Topics (Search for Journal in Brave)

Abstract: Let $mathrmR$ be a real closed field and $mathrmDsubsetmathrmR$ an ordered domain. We consider the algorithmic problem of computing the generalized Euler-Poincar'e characteristic of real algebraic as well as semi-algebraic subsets of $mathrm{R}^k$, which are defined by symmetric polynomials with coefficients in $mathrmD$. We give algorithms for computing the generalized Euler-Poincar'e characteristic of such sets, whose complexities measured by the number the number of arithmetic operations in $mathrmD$, are polynomially bounded in terms of $k$ and the number of polynomials in the input, assuming that the degrees of the input polynomials are bounded by a constant. This is in contrast to the best complexity of the known algorithms for the same problems in the non-symmetric situation, which are singly exponential. This singly exponential complexity for the latter problem is unlikely to be improved because of hardness result ($$-hardness) coming from discrete complexity theory.

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

Mathematics Subject Classification ID

Topology of real algebraic varieties (14P25) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Cites Work

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the positivity of symmetric polynomial functions. I: General results
• On the degree and half-degree principle for symmetric polynomials
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
• Euler integration over definable functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Operations on constructible functions
• Constructible motivic functions and motivic integration
• A formula for the Euler characteristic of a real algebraic manifold
• Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• Computing roadmaps of semi-algebraic sets on a variety
• Construction of roadmaps in semi-algebraic sets
• Counting connected components of a semialgebraic set in subexponential time
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On the Euler characteristic of semi-analytic and semi-algebraic sets
• Computing the first Betti number of a semi-algebraic set
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time
• Computing the Euler-Poincaré characteristics of sign conditions

Cited In (6)

• Title not available (Why is that?)
• An algorithm to compute certain Euler characteristics and Chern-Schwartz-MacPherson classes
• On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms
• Faster real root decision algorithm for symmetric polynomials
• Computing the Euler-Poincaré characteristics of sign conditions
• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets

   Recommendations

• Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities 👍 👎
• Algorithms for computing characters for symmetric spaces 👍 👎
• Computing characteristic polynomials of hyperplane arrangements with symmetries 👍 👎
• An algorithm to compute certain Euler characteristics and Chern-Schwartz-MacPherson classes 👍 👎
• Algorithms for the character theory of the symmetric group 👍 👎
• Efficient algorithms for computing the characteristic polynomial in a domain 👍 👎
• An algebraic formula for the Euler characteristic of some semi-algebraic sets 👍 👎
• A Numerical Approach for Computing Euler Characteristics of Affine Varieties 👍 👎
• Implementation of algorithms for computing characters for symmetric spaces 👍 👎
• Algorithms for Computations in Local Symmetric Spaces 👍 👎

This page was built for publication: Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635358)