Search for: All records

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 17$$\thth$$ Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, B\"{u}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^3\log^2(n\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.