Complexity lower bounds for randomized computation trees over zero characteristic fields

Abstract.

We obtain nonlinear complexity lower bounds for randomized computation trees with branching signs $\{=,\not=\}$ over zero charac-teristic fields. As consequences we get the $\Omega(n\,{\rm log}\,n)$ lower bound for the distinctness problem and $\Omega (n^2)$ lower bound for the knapsack problem. For more customary randomized computation trees over the reals with branching signs $\{\le, >\}$, similar bounds were proved: for the knapsack problem in Grigoriev & Karpinski (1997) and for the distinctness problem in Grigoriev (1999).