99-36: Randomized Complexity of Linear Arrangements and Polyhedra

DIMACS TR: 99-36

Randomized Complexity of Linear Arrangements and Polyhedra

Author: Marek Karpinski

ABSTRACT
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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-36.ps.gz

DIMACS Home Page