Capabilities and complexity of computations with integer division - Lürwer-Brüggemeier, Katharina; Meyer auf der Heide, Friedhelm (Lecture Notes in Computer Science)

Periodic Sorting on Two-Dimensional Meshes - Kutylowski, Miroslaw; Wanka, Rolf (Parallel Processing Letters 2)
We consider the following periodic sorting procedure on two-dimensional meshes of processors: Initially, each node contains one number. We proceed in rounds each round consisting of sorting the columns of the grid, and, in the second phase, of sorting the rows according to the snake-like ordering. We exactly characterize the number of rounds necessary to sort on an l × m-grid in the worst case, where l is the number of the rows and m the number of the columns. An upper bound of ⌈ log l⌉ + 1was known before. This bound is tight for the case that m is not a power of 2. Surprisingly, it turns out that far fewer rounds are necessary if m is a power of 2 (and m ≪ l) in this case, exactly min { log m + 1, ⌈ log l⌉ + 1} rounds are needed in the worst case.

High performance universal hashing, with applications to shared memory simulations - Dietzfelbinger, Martin; Meyer auf der Heide, Friedhelm (Data structures and efficient algorithms)

Hashing strategies for simulating shared memory on distributed memory machines - Meyer auf der Heide, Friedhelm (Lecture Notes in Computer Science)

On the performance of networks with multiple busses - Meyer auf der Heide, Friedhelm; Pham, Hieu Thien (STACS 92)

Efficient PRAM simulation on a distributed memory machine - Karp, Richard M.; Luby, Michael; Meyer auf der Heide, Friedhelm (Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92)

Dynamic Hashing in Real Time - Dietzfelbinger, Martin; Meyer auf der Heide, Friedhelm (TEUBNER-TEXTE zur Informatik)

Approximation of convex polygons - Alt, Helmut; Blömer, Johannes; Wagener, Hubert (Automata, Languages and Programming)

A new universal class of hash functions and dynamic hashing in real time - Dietzfelbinger, Martin; Meyer auf der Heide, Friedhelm (Automata, Languages and Programming)

Dynamic hashing strategies - Meyer auf der Heide, Friedhelm (Lecture Notes in Computer Science)

On the complexity of genuinely polynomial computation - Karpinski, Marek; Meyer auf der Heide, Friedhelm (Lecture Notes in Computer Science)

How to distribute a dictionary in a complete network - Dietzfelbinger, M.; Meyer auf der Heide, Friedhelm (Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90)

Not all keys can be hashed in constant time - Gil, J.; Meyer auf der Heide, Friedhelm; Wigderson, A. (Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90)

Das Heinz Nixdorf-Institut der Universität-GH Paderborn - Meyer auf der Heide, Friedhelm (Informatik Spektrum)

On computations with integer division - Just, Bettina; Meyer auf der Heide, Friedhelm; Wigderson, Avi (RAIRO - Theoretical Informatics and Applications)

An optimal parallel dictionary - Dietzfelbinger, M.; Meyer auf der Heide, Friedhelm (Proceedings of the first annual ACM symposium on Parallel algorithms and architectures - SPAA '89)

On genuinely time bounded computations - Meyer auf der Heide, Friedhelm (STACS 89)

Time-optimal simulations of networks by universal parallel computers - Meyer auf der Heide, Friedhelm; Wanka, Rolf (STACS 89)

Computing minimum spanning forests on 1- and 2-dimensional processor arrays - Meyer auf der Heide, Friedhelm (STACS 89)

On the limits of computations with the floor function - Babai, László; Just, Bettina; Meyer auf der Heide, Friedhelm (Information and Computation)

Fast algorithms for N-dimensional restrictions of hard problems - Meyer auf der Heide, Friedhelm (Journal of the ACM (JACM))

A tradeoff between search and update time for the implicit dictionary problem - Borodin, Allan; Fich, Faith E.; Meyer auf der Heide, Friedhelm; Upfal, Eli; Wigderson, Avi (Theoretical Computer Science)

Dynamic perfect hashing: upper and lower bounds - Dietzfelbinger, M.; Karlin, A.; Mehlhorn, K.; Meyer auf der Heide, Friedhelm; Rohnert, H.; Tarjan, R.E. ([Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science)

On computations with integer division - Just, Bettina; Mathematik, Fb; Meyer auf der Heide, Friedhelm; Informatik, Fb; Wigderson, Avi (STACS 88)

Upper and lower bounds for the dictionary problem - Dietzfelbinger, M.; Mehlhorn, K.; Meyer auf der Heide, Friedhelm; Rohnert, H. (SWAT 88)

A Time-Space Tradeoff for Element Distinctness - Borodin, A.; Fich, F.; Meyer auf der Heide, Friedhelm; Upfal, E.; Wigderson, A. (SIAM Journal on Computing)

The Complexity of Parallel Sorting - Meyer auf der Heide, Friedhelm; Wigderson, Avi (SIAM Journal on Computing)

Efficient Simulations among Several Models of Parallel Computers - Meyer auf der Heide, Friedhelm (SIAM Journal on Computing)

A tradeoff between search and update time for the implicit dictionary problem - Borodin, Allan; Fich, Faith E.; Meyer auf der Heide, Friedhelm; Upfal, Eli; Wigderson, Avi (Automata, Languages and Programming)

Speeding up random access machines by few processors - Meyer auf der Heide, Friedhelm (STACS 86)

A time-space tradeoff for element distinctness - Borodin, A.; Fich, F.; Meyer auf der Heide, Friedhelm; Upfal, E.; Wigderson, A. (STACS 86)

Lower time bounds for integer programming with two variables - Lautemann, Clemens; Meyer auf der Heide, Friedhelm (Information Processing Letters)

Lower bounds for solving linear diophantine equations on random access machines - Meyer auf der Heide, Friedhelm (Journal of the ACM (JACM))

Simulating probabilistic by deterministic algebraic computation trees - Meyer auf der Heide, Friedhelm (Theoretical Computer Science)

The complexity of parallel sorting - Meyer auf der Heide, Friedhelm; Wigderson, Avi (26th Annual Symposium on Foundations of Computer Science (sfcs 1985))

One, two, three . . . infinity: lower bounds for parallel computation - Fich, F E; Meyer auf der Heide, Friedhelm; Ragde, P; Wigderson, A (Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85)

Fast algorithms for n-dimensional restrictions of hard problems - Meyer auf der Heide, Friedhelm (Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85)

Nondeterministic versus probabilistic linear search algorithms - Meyer auf der Heide, Friedhelm (26th Annual Symposium on Foundations of Computer Science (sfcs 1985))

Lower time bounds for solving linear diophantine equations on several parallel computational models - Meyer auf der Heide, Friedhelm (Information and Control)

A Polynomial Linear Search Algorithm forr the n-Dimensional Knapsack Problem - Meyer auf der Heide, Friedhelm (Journal of the ACM (JACM))

On The Limits To Speed Up Parallel Machines By Large Hardware And Unbounded Communication - Meyer auf der Heide, Friedhelm; Reischuk, R. (25th Annual Symposium onFoundations of Computer Science, 1984.)

Efficient simulations among several models of parallel computers (extended abstract) - Meyer auf der Heide, Friedhelm (STACS 84)

Efficiency of universal parallel computers - Meyer auf der Heide, Friedhelm (Acta Informatica)

A lower time bound for the knapsack problem on random access machines - Klein, Peter; Meyer auf der Heide, Friedhelm (Acta Informatica)

Infinite cube-connected cycles - Meyer auf der Heide, Friedhelm (Information Processing Letters)

A polynomial linear search algorithm for the n-dimensional knapsack problem - Meyer auf der Heide, Friedhelm (Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83)

Efficiency of universal parallel computers - Meyer auf der Heide, Friedhelm (Lecture Notes in Computer Science)

Random access machines and straight-line programs - Meyer auf der Heide, Friedhelm; Rollik, Anton (Fundamentals of Computation Theory)

Time-processor trade-offs for universal parallel computers - Meyer auf der Heide, Friedhelm (Lecture Notes in Computer Science)

A comparison of two variations of a pebble game on graphs - Meyer auf der Heide, Friedhelm (Theoretical Computer Science)