Efficient evaluation of specific queries in constraint databases

Let F1,…,Fs∈R[X1,…,Xn]F1,…,Fs∈R[X1,…,Xn] be polynomials of degree at most d  , and suppose that F1,…,FsF1,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L  . Let AA be the arrangement of RnRn defined by F1,…,FsF1,…,Fs.For any point x∈Rnx∈Rn, we consider the task of determining the signs of the values F1(x),…,Fs(x)F1(x),…,Fs(x) (sign condition query) and the task of determining the connected component of AA to which x   belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F1,…,FsF1,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n)sO(L+n) which allows the evaluation of the sign condition query using only (Ln)O(1)log(s)(Ln)O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s)dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F1,…,FsF1,…,Fs belong to Z[X1,…,Xn]Z[X1,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F1,…,FsF1,…,Fs.

► There is given an arithmetic circuit of size L computing a family of s polynomials. ► We study the sign-condition problem for this family of polynomials in n   variables. ► We solve this problem performing only log(s)(Ln)O(1)log(s)(Ln)O(1) operations. ► We show that this upper bound is almost optimal. ► We study also the corresponding point-location problem.