TR96-058 Authors: Dima Grigoriev, Marek Karpinski

Publication: 25th November 1996 13:48

Downloads: 969

Keywords:

We prove $\Omega (n^2)$ complexity \emph{lower bound} for the

general model of \emph{randomized computation trees} solving

the \emph{Knapsack Problem}, and more generally \emph{Restricted

Integer Programming}. This is the \emph{first nontrivial} lower

bound proven for this model of computation. The method of the

proof depends crucially on the new technique for proving lower

bounds on the \emph{border complexity} of a polynomial which

could be of independent interest.