On the complexity of genuinely polynomial computation
M. Karpinski, F. Meyer auf der Heide, in: Lecture Notes in Computer Science, Berlin/Heidelberg, 1990.

How to distribute a dictionary in a complete network
M. Dietzfelbinger, F. Meyer auf der Heide, in: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing  - STOC ’90, 1990.

Not all keys can be hashed in constant time
J. Gil, F. Meyer auf der Heide, A. Wigderson, in: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing  - STOC ’90, 1990.

Das Heinz Nixdorf-Institut der Universität-GH Paderborn
F. Meyer auf der Heide, Informatik Spektrum 13 (1990) 231–232.

On computations with integer division
B. Just, F. Meyer auf der Heide, A. Wigderson, RAIRO - Theoretical Informatics and Applications (1989) 101–111.

An optimal parallel dictionary
M. Dietzfelbinger, F. Meyer auf der Heide, in: Proceedings of the First Annual ACM Symposium on Parallel Algorithms and Architectures  - SPAA ’89, 1989.

On genuinely time bounded computations
F. Meyer auf der Heide, in: STACS 89, Berlin/Heidelberg, 1989.

Time-optimal simulations of networks by universal parallel computers
F. Meyer auf der Heide, R. Wanka, in: STACS 89, Berlin/Heidelberg, 1989.

Computing minimum spanning forests on 1- and 2-dimensional processor arrays
F. Meyer auf der Heide, in: STACS 89, Berlin, Heidelberg, 1989.

On the limits of computations with the floor function
L. Babai, B. Just, F. Meyer auf der Heide, Information and Computation (1988) 99–107.