TU Berlin

Fachgebiet Algorithmische AlgebraJournal Publications

Page Content

to Navigation

There is no English translation for this web page.

Journal Publications

On the parallel complexity of the polynomial ideal membership problem
Citation key B-On-The-Parallel-Complexity-Of-The-Polynomial-Ideal-Membership-Problem
Author Peter Bürgisser
Pages 176-189
Year 1998
Journal J. Compl.
Volume 14
Abstract The complexity of the polynomial ideal membership problem over arbitrary fields within the framwork of arithmetic networks is investigated. We prove that the parallel complexity of this problem is single exponential over any infinite field. Our lower bound is obtained by combining a modification of Mayr and Meyer's key construction (1982) with an elementary degree bound.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe