@inproceedings{LickteigMeerPardo, author = {Lickteig, Thomas and Meer, Klaus and Pardo, Luis Miguel}, title = {Real Computation and Complexity, Dagstuhl seminar}, publisher = {Internationale Begegnungs- und Forschungszentrum f{\"u}r Informatik}, address = {Dagstuhl}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-4994}, language = {en} } @misc{MeerLickteig, author = {Meer, Klaus and Lickteig, Thomas}, title = {Semi-algebraic complexity - Additive complexity of matrix computational tasks}, series = {Journal of Complexity}, volume = {13}, journal = {Journal of Complexity}, number = {1}, issn = {0885-064X}, doi = {10.1006/jcom.1997.0430}, pages = {83 -- 107}, abstract = {This paper is devoted to the study of lower bounds on the inherent number of additions and subtractions necessary to solve some natural matrix computational tasks such as computing the nullspace, some band transformation, and some triangulation of a givenmĂ—mmatrix. The additive complexities of such tasks are shown to grow asymptotically like that of themĂ—mmatrix multiplication. The paper is a continuation of an earlier paper by the authors, and also of 4where multiplicative complexity has been considered. We also propose a formalization of semialgebraic computational tasks.}, language = {en} } @misc{MeerLickteig, author = {Meer, Klaus and Lickteig, Thomas}, title = {A note on testing the resultant}, series = {Journal of Complexity}, volume = {11}, journal = {Journal of Complexity}, number = {3}, issn = {0885-064X}, doi = {10.1006/jcom.1995.1016}, pages = {344 -- 351}, abstract = {Shub (in "From Topology to Computation: Proceedings of the Smalefest." (M. Hirsch, J. Marsden, and M. Shub, Eds.), pp. 281-301, Springer-Verlag, New York/Berlin, 1993) proposes to attack the complex PFull-size image (<1 K) versus the NPFull-size image (<1 K) problem by focussing on lower bounds on testing the resultant of quadratic forms for zero. Taking up this question we show in the present paper a lower bound of order n3 for the resultant.}, language = {en} }