Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1999 Copyright 1999 Universität Bonn, Institut für Informatik, Abt. V
85205

Randomized Complexity of Linear Arrangements and Polyhedra
Marek Karpinski
[Download PostScript] [Download PDF]

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 K Bounded Integer Programming. We formulate further several open problems and possible directions for future research.

Last Change: 11/05/14 at 10:14:53
 English
Universität Bonn -> Institut für Informatik -> Abteilung V