DIMACS TR: 99-36
Randomized Complexity of Linear Arrangements and Polyhedra
Author: 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, randomized lower bounds on the problems like Knapsack
and Bounded Integer Programming. We formulate further several
open problems and possible directions for future research.
Paper Available at:
DIMACS Home Page