Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ARRANGEMENTS:
Reports tagged with Arrangements:
TR96-058 | 25th November 1996
Dima Grigoriev, Marek Karpinski

Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

We 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 ... more >>>




ISSN 1433-8092 | Imprint