Dima Grigoriev, Marek Karpinski

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

Marek Karpinski

We survey some of the recent results on the complexity of recognizing

n-dimensional linear arrangements and convex polyhedra by randomized

algebraic decision trees. We give also a number of concrete applications

of these results. In particular, we derive first nontrivial, in fact

quadratic, ...
more >>>

Parikshit Gopalan, Adam Klivans, Raghu Meka

We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with total weight W and accuracy parameter eps, our algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log W,1/eps). We also give algorithms ... more >>>

Stasys Jukna

We consider so-called ``incremental'' dynamic programming (DP) algorithms, and are interested in the number of subproblems produced by them. The standard DP algorithm for the n-dimensional Knapsack problem is incremental, and produces nK subproblems, where K is the capacity of the knapsack. We show that any incremental algorithm for this ... more >>>