Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

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

Valentin E. Brimkov, Stefan S. Dantchev

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

Valentin E. Brimkov, Stefan S. Dantchev

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