Search for: All records

Suppose A = {a 1 , . . . , a n+2 } ⊂ Z n has cardinality n + 2, with all the coordinates of the a j having absolute value at most d, and the a j do not all lie in the same affine hyperplane. Suppose F = ( f 1 , . . . , f n ) is an n × n polynomial system with generic integer coefficients at most H in absolute value, and A the union of the sets of exponent vectors of the f i . We give the first algorithm that, for any fixed n, counts exactly the number of real roots of F in time polynomial in log(dH ). We also discuss a number- theoretic hypothesis that would imply a further speed-up to time polynomial in n as well. 

We consider the sensitivity of real zeros of structured polynomial systems to pertubations of their coefficients. In particular, we provide explicit estimates for condition numbers of structured random real polynomial systems and extend these estimates to the smoothed analysis setting. 

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.