Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SET DISJOINTNESS:
Reports tagged with Set Disjointness:
TR99-020 | 9th June 1999
Marek Karpinski

#### Randomized Complexity of Linear Arrangements and Polyhedra

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