BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Peter Bürgisser (TU Berlin)
DTSTART:20201110T173000Z
DTEND:20201110T180000Z
DTSTAMP:20260423T041750Z
UID:LA-CoCo/9
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/LA-CoCo/9/">
 Complexity of computing zeros of structured polynomial systems</a>\nby Pet
 er Bürgisser (TU Berlin) as part of LA Combinatorics and Complexity Semin
 ar\n\n\nAbstract\nCan we solve polynomial systems in polynomial time?  Thi
 s question\nreceived different answers in different contexts.  The <b>NP</
 b>-completeness\nof deciding the feasibility of a general polynomial syste
 m in both\nTuring and BSS models of computation is certainly an important\
 ndifficulty but it does not preclude efficient algorithms for\ncomputing a
 ll the roots of a polynomial system or solving\npolynomial systems with as
  many equations as variables\, for which the\nfeasibility over algebraical
 ly closed fields is granted under\ngenericity hypotheses.  And indeed\, th
 ere are several ways of\ncomputing all $\\delta^n$ zeros of a generic poly
 nomial system of $n$\nequations of degree $\\delta > 1$ in $n$ variables w
 ith\n$\\operatorname{poly}(\\delta^n)$ arithmetic operations. \n\n<i>Smale
 's 17th problem</i> is a clear-cut formulation\nof the problem in a numeri
 cal setting.  It asks for an algorithm\, with\npolynomial average complexi
 ty\, for computing <i>one</i> approximate zero of a\ngiven polynomial syst
 em\, where the complexity is to be measured with\nrespect to the <i>dense 
 input size</i> $N$\, that is\, the number of\npossible monomials in the in
 put system.\n\nWe design a probabilistic algorithm that\, on input $\\epsi
 lon>0$ and a polynomial\n  system $F$ given by black-box evaluation functi
 ons\, outputs an approximate\n  zero of $F$\, in the sense of Smale\, with
  probability at least $(1-\\epsilon)$.\n  When applying this algorithm to 
 $u \\cdot F$\, where $u$ is uniformly random in\n  the product of unitary 
 groups\, the algorithm performs\n  $\\operatorname{poly}(n\, \\delta) \\cd
 ot L(F) \\cdot \\left( \\Gamma(F) \\log \\Gamma(F) + \\log \\log \\epsilon
 ^{-1} \\right)$\n  operations on average. Here $n$ is the number of variab
 les\, $\\delta$ the\n  maximum degree\, $L(F)$ denotes the evaluation cost
  of $F$\, and $\\Gamma(F)$\n  reflects an aspect of the numerical conditio
 n of $F$. Moreover\, we prove that\n  for inputs given by random Gaussian 
 algebraic branching programs of\n  size $\\operatorname{poly}(n\,\\delta)$
 \, the algorithm runs on average in time\n  polynomial in $n$ and $\\delta
 $. Our result may be interpreted as an\n  affirmative answer to a refined 
 version of Smale's 17th problem\, concerned\n  with systems of <i>structur
 ed</i> polynomial equations.\n\nThis is joint work with Felipe Cucker and 
 Pierre Lairez.  \nThe talk will not go into technical details and will be 
 accessible to the general audience.\n
LOCATION:https://researchseminars.org/talk/LA-CoCo/9/
END:VEVENT
END:VCALENDAR