ECCC-Report TR96-058https://eccc.weizmann.ac.il/report/1996/058Comments and Revisions published for TR96-058en-usMon, 25 Nov 1996 13:48:49 +0200
Paper TR96-058
| Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack |
Dima Grigoriev,
Marek Karpinski
https://eccc.weizmann.ac.il/report/1996/058We 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.
Mon, 25 Nov 1996 13:48:49 +0200https://eccc.weizmann.ac.il/report/1996/058