Randomized Omega (n^2) Lower Bound for Knapsack

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.