On the topology of algorithms. I (Q1099953)

The author considers the following problem: Poly(d): Given a complex polynomial f of degree d and with leading coefficient 1, find all the roots of f within \(\epsilon >0\). He defines the topological complexity of a problem as the minimum of the numbers of branching nodes of the computation trees describing the algorithms which solve that problem. The following result is derived in this paper: There exists in each dimension d an \(\epsilon (d)>0\) such that for all \(\epsilon <\epsilon (d)\) the topological complexity of the problem Poly(d) is greater than \((\log_ 2 d)^{2/3}.\) The proof uses techniques of algebraic topology. As a first step, it is shown that the topological complexity of Poly(d) is greater or equal the covering number of \(\pi\) : \({\mathbb{C}}^ d-\Delta \to {\mathcal P}_ d- \Sigma\), where \({\mathcal P}_ d\) is the space of all complex polynomials of degree d with leading coefficient fractional cascading, a new searching technique which has been described in a companion paper (see the preceding review). The applications center around a variety of geometric query problems. Examples include intersecting a polygonal path with a line, slanted range search, orthogonal range search, computing locus functions, and others. Some results on the optimality of fractional cascading, and certain extensions of the technique for retrieving additional information are also included.