BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:One block quantifier elimination over the reals: algorithms\, comp
lexity and applications
DTSTART;VALUE=DATE-TIME:20210930T083000Z
DTEND;VALUE=DATE-TIME:20210930T093000Z
DTSTAMP;VALUE=DATE-TIME:20211022T220128Z
UID:indico-event-6783@indico.math.cnrs.fr
DESCRIPTION:Quantifier elimination over the reals is one of the central\na
lgorithmic problem in effective real algebraic geometry. Given a\nquantifi
ed semi-algebraic formula\, it consists in computing a\nlogically equivale
nt quantifier-free formula.\n\nIn this task\, I will describe a new effici
ent algorithm for one block\nquantifier elimination under some mild assump
tions. This computes\nsemi-algebraic formulas which describe a dense subse
t of the interior\nof the projection of a given real algebraic set on a su
bset of\ncoordinates. Interestingly\, the output formula enjoys a determin
antal\nstructure which make them easy to evaluate.\n\nUnder some genericit
y assumptions\, we use the theory of Groebner bases\nto prove that our alg
orithm runs in time $O(8^t D^{4nt})$ where $D$\nbounds the degree of the i
nput variables\, $n$ is the number of\nquantified variables and $t$ the nu
mber of parameters. Note that\, by\ncontrast with the classical Cylindrica
l Algebraic Decomposition\nalgorithm (which is doubly exponential in $n$ a
nd $t$)\, our algorithm\nruns in time singly exponential.\n\nWe report on
extensive practical experiments and show that our\nimplementation outperfo
rms the state-of-the-art software.\n\nOur algorithm relies on properties o
f Groebner bases\, specialization\nproperties of Hermite quadratic forms (
a tool for real root counting)\nand new algorithms for solving zero-dimens
ional parametric systems.\n\nNext\, we show how to apply our contributions
to compute the totally\nreal hyperplane sections coming from the theory o
f real algebraic\ncurves.\n\nThis talk gathers joint works with Dimitri Ma
nevich\, Daniel Plaumann\nand Mohab Safey El Din.\n\nhttps://indico.math.c
nrs.fr/event/6783/
LOCATION:https://bbb.unilim.fr/b/vac-m6r-7dv
URL:https://indico.math.cnrs.fr/event/6783/
END:VEVENT
END:VCALENDAR