Randomized complexity lower bounds
| Author(s) : | D. Grigoriev, |
| Publisher : | N/A |
| Publication Date : | 1998 |
| ISSN : | N/A |
| Abstract : | The complexity lower bound \Omega\Gammand / N) is proved for randomized computation trees (over reals with branching signs f;?g) for recognizing an arrangement or a polyhedron with N faces. A similar lower bound is proved for randomized computation trees over any zero-characteristic field with branching signs f=; 6=g for recognizing an arrangement. As consequences, this provides in particular, the randomized lower bound \Omega\Gamma, |