Title: A Faster Solution to Smale's 17th Problem I: Real Binomial Systems,
Abstract: Suppose $F:=(f_1,\ldots,f_n)$ is a system of random $n$-variate polynomials
with $f_i$ having degree $\leq\!d_i$ and the coefficient of $x^{a_1}_1\cdots
x^{a_n}_n$ in $f_i$ being an independent complex Gaussian of mean $0$ and
variance $\frac{d_i!}{a_1!\cdots a_n!\left(d_i-\sum^n_{j=1}a_j \right)!}$.
Recent progress on Smale's 17th Problem by Lairez --- building upon seminal
work of Shub, Beltran, Pardo, Bürgisser, and Cucker --- has resulted in a
deterministic algorithm that finds a single (complex) approximate root of $F$
using just $N^{O(1)}$ arithmetic operations on average, where
$N\!:=\!\sum^n_{i=1}\frac{(n+d_i)!}{n!d_i!}$ ($=n(n+\max_i
d_i)^{O(\min\{n,\max_i d_i)\}}$) is the maximum possible total number of
monomial terms for such an $F$. However, can one go faster when the number of
terms is smaller, and we restrict to real coefficient and real roots? And can
one still maintain average-case polynomial-time with more general probability
measures?
We show the answer is yes when $F$ is instead a binomial system --- a case
whose numerical solution is a key step in polyhedral homotopy algorithms for
solving arbitrary polynomial systems. We give a deterministic algorithm that
finds a real approximate root (or correctly decides there are none) using just
$O(n^2(\log(n)+\log\max_i d_i))$ arithmetic operations on average. Furthermore,
our approach allows Gaussians with arbitrary variance. We also discuss briefly
the obstructions to maintaining average-case time polynomial in $n\log \max_i
d_i$ when $F$ has more terms.