Show simple item record

dc.contributor.authorRiener, Cordian
dc.contributor.authorSafey el Din, Mohab
dc.date.accessioned2023-09-08T09:16:32Z
dc.date.available2023-09-08T09:16:32Z
dc.date.issued2018
dc.description.abstractLet <i><b>R</b></i> be a real closed field. We consider basic semi-algebraic sets defined by <i>n</i>-variate equations/inequalities of s symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by 2<i>d</i> &#60; <i>n</i>. 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 2<i>d</i>−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 <i>s</i> polynomials of degree <i>d</i> in time <i>(sn)<sup>O(d)</sup></i>. This improves the state-of-the-art which is exponential in <i>n</i>. When the variables <i>x<sub>1</sub>, ..., x<sub>n</sub></i> are quantified and the coefficients of the input system depend on parameters <i>y<sub>1</sub>, ..., y<sub>t</sub></i>, one also demonstrates that the corresponding one-block quantifier elimination problem can be solved in time <i>(sn)<sup>O(d)</sup></i>.en_US
dc.identifier.cristinIDFRIDAID 1601288
dc.identifier.urihttps://hdl.handle.net/10037/30805
dc.language.isoengen_US
dc.relation.urihttps://dl.acm.org/citation.cfm?id=3209023
dc.subjectVDP::Matematikk og naturvitenskap: 400::Matematikk: 410en_US
dc.subjectVDP::Mathematics and natural scienses: 400::Mathematics: 410en_US
dc.titleReal Root Finding for Equivariant Semi-algebraic Systemsen_US
dc.typeConference objecten_US
dc.typeKonferansebidragen_US


File(s) in this item

Thumbnail

This item appears in the following collection(s)

Show simple item record