We extend the lower bounds on the depth of algebraic decision trees to the case of {\em randomized} algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, ... more >>>

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$) $a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework of the Blum-Shub-Smale real number computational model \cite{BSS}. We obtain a new lower bound $\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time complexity of this problem, as well ... more >>>

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem (ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors $b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x \in ... more >>>