Lower bounds for algebraic computation trees of functions with finite domains
ACC Yao - SIAM Journal on Computing, 1991 - SIAM
SIAM Journal on Computing, 1991•SIAM
Let W⊆R^n be scale-invariant and rationally dispersed, ie, ̃x∈W implies λ̃x∈W for all real
λ>0; and the rationale are dense in both W and R^nW. It is shown that, in the algebraic
computation tree model, the problem of deciding whether an input ̃x∈R^n with integer
coordinates is a member of W has complexity Ω(\log_2̂β(W)-2n), where ̂β(W) is the
number of connected components of W that are not of measure 0. This theorem can be used
to prove tight lower bounds for the integral-constrained form of many basic problems, such …
λ>0; and the rationale are dense in both W and R^nW. It is shown that, in the algebraic
computation tree model, the problem of deciding whether an input ̃x∈R^n with integer
coordinates is a member of W has complexity Ω(\log_2̂β(W)-2n), where ̂β(W) is the
number of connected components of W that are not of measure 0. This theorem can be used
to prove tight lower bounds for the integral-constrained form of many basic problems, such …
Let be scale-invariant and rationally dispersed, i.e., implies for all real ; and the rationale are dense in both W and . It is shown that, in the algebraic computation tree model, the problem of deciding whether an input with integer coordinates is a member of W has complexity , where is the number of connected components of W that are not of measure 0. This theorem can be used to prove tight lower bounds for the integral-constrained form of many basic problems, such as Element Distinctness, Set Disjointness, Finding Convex Hull, etc. Through further transformations, it leads to lower bounds for problems such as Integer Max Gap and Closest Pair of a simple polygon. The proof involves a nontrivial extension of the Milnor–Thorn techniques for finding upper bounds on the Betti numbers of algebraic varieties.