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 ... 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 ... 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 ... more >>>