BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Amortized complexity bounds for polynomials with algebraic coeffic
 ients and application to curve topology
DTSTART:20261008T120000Z
DTEND:20261008T140000Z
DTSTAMP:20261011T094000Z
UID:indico-event-16690@indico.math.cnrs.fr
DESCRIPTION:Speakers: Daouda Diatta\n\nLet $P \\in \\mathbb{Z} [X\, Y]$ be
  a square-free polynomial of total degree $d$ and coefficients of bitsize\
 n $\\tau$\, and $\\mathcal{C}(P) := \\{ (x\,y) \\in \\mathbb{R}^2\, P (x\
 ,y)= 0 \\}$ be the real algebraic curve defined by $P$. \nWe describe an 
 algorithm performing no change of variable and computing the topology of 
 $\\mathcal{C} (P)$ $i.e$ a\n straight-line planar graph isotopic to $\\ma
 thcal{C} (P)$ inside $\\mathbb{R}^2$ in $\\tilde{O} (d^5 \\tau\n + d^6)$ 
 bit operations. Compared to state of the art algorithms used for computi
 ng a Cylindrical Algebraic Decomposition\, this result avoids entirely a 
 generic shear. \nOur result is based on two main ingredients:First\, we d
 erive amortized quantitative bounds on the roots of polynomials with algeb
 raic coefficients as well as adaptive methods for computing the roots of 
 bivariate polynomial systems that actually exploit this amortization. Our 
 second ingredient is a novel approach for the computation of the local top
 ology of the curve in a neighborhood of all singular points.\n\nhttps://in
 dico.math.cnrs.fr/event/16690/
LOCATION:Salle de conférences (LJAD)
URL:https://indico.math.cnrs.fr/event/16690/
END:VEVENT
END:VCALENDAR