Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1996 Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V
85158

Randomized Omega(n*n) Lower Bound for Knapsack
Dima Grigoriev, Marek Karpinski
[Download PostScript] [Download PDF]

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.

Last Change: 11/05/14 at 10:00:47
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope