Evaluating geometric queries using few arithmetic operations

Abstract

Let P:=(P1,...,Ps) be a given family of n-variate polynomials with integer coefficients and suppose that the degrees and logarithmic heights of these polynomials are bounded by d and h, respectively. Suppose furthermore that for each i=1...s the polynomial Pi can be evaluated using L arithmetic operations (additions, subtractions, multiplications and the constants 0 and 1). Assume that the family P is in a suitable sense generic. We construct a database D , supported by an algebraic computation tree, such that for each x in [0,1]^n the query for the signs of P1(x),..., Ps(x) can be answered using h^d^O(n2) comparisons and nL arithmetic operations between real numbers. The arithmetic-geometric tools developed for the construction of D are then employed to exhibit example classes of systems of n polynomial equations in n unknowns whose consistency may be checked using only few arithmetic operations, admitting, however, an exponential number of comparisons.