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