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