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 1 ≤ i ≤ s the polynomial P i 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∈[0,1]n the query for the signs of P 1(x), . . . , P s (x) can be answered using hdO(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.