Name
Abstract | ||
|---|---|---|
Let R be a real closed field. We consider basic semi-algebraic sets defined by n-variate equations/inequalities of s symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by 2d < n. Such a semi-algebraic set is invariant by the action of the symmetric group. We show that such a set is either empty or it contains a point with at most 2d -1 distinct coordinates. Combining this geometric result with efficient algorithms for real root finding (based on the critical point method), one can decide the emptiness of basic semi-algebraic sets defined by s polynomials of degree d in time (sn)(O(d)). This improves the state-of-the-art which is exponential in n. When the variables x(1), ..., x(n) are quantified and the coefficients of the input system depend on parameters y(1), ..., y(t), one also demonstrates that the corresponding one-block quantifier elimination problem can be solved in time (sn)(O(dt)). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3208976.3209023 | ISSAC'18: PROCEEDINGS OF THE 2018 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION |
Keywords | DocType | Volume |
Symmetric group, Semi-algebraic sets, Polynomial system solving | Journal | abs/1806.08121 |
ISSN | Citations | PageRank |
Proceedings of the International Symposium on Symbolic and
Algebraic Computation, 2018, New-York, United States | 0 | 0.34 |
References | Authors | |
23 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cordian Riener | 1 | 7 | 3.38 |
| Mohab Safey El Din | 2 | 450 | 35.64 |