Randomized ?(n^2) Lower Bound for Knapsack

TitleRandomized ?(n^2) Lower Bound for Knapsack
Publication TypeTechnical Report
Year of Publication1996
AuthorsGrigoriev, D. Yu., & Karpinski M.
Other Numbers1059

We prove ?(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.

Bibliographic Notes

ICSI Technical Report TR-96-050

Abbreviated Authors

D. Grigoriev and M. Karpinski

ICSI Publication Type

Technical Report