DIMACS TR: 96-52
Randomized Omega (n^2) Lower Bound for Knapsac
Authors: Dima Grigoriev, Marek Karpinski
ABSTRACT
We prove Omega (n^2) complexity lower bound for the
general model of randomized computation trees solving
the Knapsack Problem, and more generally Restricted
Integer Programming. This is the 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 border complexity of a polynomial which could be of
independent interest.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-52.ps.gz
DIMACS Home Page