Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-020 | 9th June 1999 00:00

Randomized Complexity of Linear Arrangements and Polyhedra

RSS-Feed

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.



ISSN 1433-8092 | Imprint