@inbook{16693, author = {{Meyer auf der Heide, Friedhelm and Decker, Thomas}}, booktitle = {{Informatik ’97 Informatik als Innovationsmotor}}, isbn = {{9783540630661}}, issn = {{1431-472X}}, title = {{{Parallel Computing in Paderborn: The SFB 376 “Massive Parallelism — Algorithms, Design Methods, Applications”}}}, doi = {{10.1007/978-3-642-60831-5_22}}, year = {{1997}}, } @article{19958, author = {{Schwarze, Frank and Meyer auf der Heide, Friedhelm and Schröder, Klaus}}, journal = {{Euro-Par 1996}}, pages = {{299--306}}, title = {{{Routing on Networks of Optical Crossbars (Extended Abstract).}}}, volume = {{I}}, year = {{1996}}, } @techreport{17418, author = {{Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker}}, title = {{{Contention Resolution in Hashing Based Shared Memory Simulations}}}, year = {{1996}}, } @inproceedings{17419, abstract = {{We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality.}}, author = {{Grigoriev, Dima and Karpinski, Marek and Meyer auf der Heide, Friedhelm and Smolensky, Roman}}, booktitle = {{Proc. of 28th ACM-STOC}}, pages = {{612--621}}, publisher = {{Eurographics Symposium on Parallel Graphics and Visualization}}, title = {{{A lower bound for randomized algebraic decision trees}}}, volume = {{65453}}, year = {{1996}}, } @inproceedings{17483, abstract = {{In this paper we develop a model for communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. The implementation of the service network is done on a free configurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multi-linear function. The cost model includes the parameters packet size, send hot spot, and the number of processors accessing global variables. These parameters influence the communication time in a high degree and capture important parameters like contention. We implement a Bitonic Sort and a Connected Components algorithm (among others) and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programmer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines on-line the optimal parameter values for an access to a global variable achieves good speed ups.}}, author = {{Fischer, Matthias and Rethmann, Jochen and Wachsmann, Alf}}, booktitle = {{3rd Workshop on Abstract Machine Models for Parallel and Distributed Computing (AMW '96)}}, isbn = {{905199267X}}, pages = {{13–27}}, publisher = {{IOS Press}}, title = {{{A Realistic Cost Model for the Communication Time in Parallel Programs}}}, year = {{1996}}, } @inbook{17564, author = {{Bäumker, Armin and Dittrich, Wolfgang and Meyer auf der Heide, Friedhelm and Rieping, Ingo}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540616276}}, issn = {{0302-9743}}, pages = {{369--376}}, title = {{{Realistic parallel algorithms: Priority queue operations and selection for the BSP* Model}}}, doi = {{10.1007/bfb0024725}}, year = {{1996}}, } @techreport{18352, abstract = {{In this report, we develop a cost model for the communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. Because we do not have a parallel computer at our disposal that is equipped with a service network, we emulate the service network on a reconfigurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multi­linear function. The cost model includes the parameters packet size, send hot spot (the number of messages sent out by one processor), and number of processors accessing global variables. We show that these parameters influence the communication time in a high degree and capture important parameters like network contention. We implement a Bitonic Sort, Sample Sort, Matrix Multiplication, and Connected Components algorithm, and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. We explore the interaction of hot spots and asynchrony and show that the influence of hot spots to the communication time is not as high as one would expect from theoretical considerations in a synchronous model. Therefore, we do not apprehend the hot spot in our cost model. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines on­line the optimal parameter values for an access to a global variable achieves good speed ups. }}, author = {{Fischer, Matthias and Rethmann, Jochen and Wachsmann, Alf}}, title = {{{A Realistic Cost Model for the Communication Time in Parallel Programs on Parallel Computers Using a Service Hardware}}}, year = {{1996}}, } @phdthesis{2181, author = {{Scheideler, Christian}}, publisher = {{University of Paderborn, Germany}}, title = {{{Universal routing strategies}}}, year = {{1996}}, } @article{2182, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian and Stemann, Volker}}, journal = {{Theor. Comput. Sci.}}, number = {{2}}, pages = {{245----281}}, title = {{{Exploiting Storage Redundancy to Speed up Randomized Shared Memory Simulations}}}, doi = {{10.1016/0304-3975(96)00032-1}}, year = {{1996}}, } @inproceedings{2183, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{FOCS}}, pages = {{370----379}}, title = {{{Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols}}}, year = {{1996}}, } @inproceedings{2184, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{SOFSEM}}, pages = {{16----33}}, publisher = {{Springer}}, title = {{{Communication in Parallel Systems}}}, volume = {{1175}}, year = {{1996}}, } @inproceedings{2186, author = {{Cypher, Robert and Meyer auf der Heide, Friedhelm and Scheideler, Christian and Vöcking, Berthold}}, booktitle = {{STOC}}, pages = {{356----365}}, publisher = {{ACM}}, title = {{{Universal Algorithms for Store-and-Forward and Wormhole Routing}}}, year = {{1996}}, } @article{16698, author = {{Ameur, Foued and Fischer, Paul and Höffgen, Klaus -U. and Meyer auf der Heide, Friedhelm}}, issn = {{0001-5903}}, journal = {{Acta Informatica}}, pages = {{621--630}}, title = {{{Trial and error. A new approach to space-bounded learning}}}, doi = {{10.1007/bf03036467}}, year = {{1996}}, } @article{16699, author = {{Meyer auf der Heide, Friedhelm and Oesterdiekhoff, Brigitte and Wanka, Rolf}}, issn = {{0178-4617}}, journal = {{Algorithmica}}, pages = {{413--427}}, title = {{{Strongly adaptive token distribution}}}, doi = {{10.1007/bf01955042}}, year = {{1996}}, } @article{16700, author = {{Karp, R. M. and Luby, M. and Meyer auf der Heide, Friedhelm}}, issn = {{0178-4617}}, journal = {{Algorithmica}}, pages = {{517--542}}, title = {{{Efficient PRAM simulation on a distributed memory machine}}}, doi = {{10.1007/bf01940878}}, year = {{1996}}, } @article{16701, author = {{Gil, Joseph and Meyer auf der Heide, Friedhelm and Wigderson, Avi}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{936--955}}, title = {{{The Tree Model for Hashing: Lower and Upper Bounds}}}, doi = {{10.1137/s0097539793255722}}, year = {{1996}}, } @book{16702, editor = {{Meyer auf der Heide, Friedhelm and Monien, Burkhard}}, isbn = {{9783540614401}}, issn = {{0302-9743}}, title = {{{Automata, Languages and Programming, 23rd International Colloquium, ICALP96}}}, doi = {{10.1007/3-540-61440-0}}, year = {{1996}}, } @inbook{16703, author = {{Berenbrink, Petra and Meyer auf der Heide, Friedhelm and Stemann, Volker}}, booktitle = {{STACS 96}}, isbn = {{9783540609223}}, issn = {{0302-9743}}, title = {{{Fault-tolerant shared memory simulations}}}, doi = {{10.1007/3-540-60922-9_16}}, year = {{1996}}, } @phdthesis{19623, author = {{Stemann, Volker}}, isbn = {{3-931466-02-7}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Contention Resolution in Hashing Based Shared Memory Simulations}}}, volume = {{3}}, year = {{1995}}, } @phdthesis{19627, author = {{Czumaj, Artur}}, isbn = {{3-931466-07-8}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Parallel Algorithmic Techniques: PRAM Algorithms and PRAM Simulations}}}, volume = {{8}}, year = {{1995}}, } @phdthesis{19630, author = {{Wachsmann, Alf}}, isbn = {{3-931466-05-1}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Eine Bibliothek von Basisdiensten für Parallelrechner: Routing, Synchronisation, gemeinsamer Speicher}}}, volume = {{6}}, year = {{1995}}, } @phdthesis{19634, author = {{Ameur, Foued}}, isbn = {{3-931466-09-4}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Space-Bounded Learning Algorithms}}}, volume = {{10}}, year = {{1995}}, } @inproceedings{17482, author = {{Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker}}, booktitle = {{Proceedings of the 2nd IEEE Workshop on Reconfigurable Architectures}}, pages = {{46----59}}, title = {{{Simulating shared memory in real time: On the computation power of reconfigurable meshes}}}, year = {{1995}}, } @inproceedings{2187, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{ESA}}, pages = {{341----354}}, title = {{{Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks}}}, doi = {{10.1007/3-540-60313-1_154}}, year = {{1995}}, } @inproceedings{2207, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{SPAA}}, pages = {{137----146}}, title = {{{Space-Efficient Routing in Vertex-Symmetric Networks (Extended Abstract)}}}, year = {{1995}}, } @inproceedings{2208, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian and Stemann, Volker}}, booktitle = {{STACS}}, pages = {{267----278}}, title = {{{Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations}}}, year = {{1995}}, } @article{16566, author = {{Breslauer, Dany and Czumaj, Artur and Dubhashi, Devdatt P. and Meyer auf der Heide, Friedhelm}}, issn = {{0020-0190}}, journal = {{Information Processing Letters}}, pages = {{103--110}}, title = {{{Transforming comparison model lower bounds to the parallel-random-access-machine}}}, doi = {{10.1016/s0020-0190(97)00032-x}}, year = {{1995}}, } @inbook{16704, author = {{Meyer auf der Heide, Friedhelm and Vöcking, Berthold}}, booktitle = {{STACS 95}}, isbn = {{9783540590422}}, issn = {{0302-9743}}, title = {{{A packet routing protocol for arbitrary networks}}}, doi = {{10.1007/3-540-59042-0_81}}, year = {{1995}}, } @inbook{16705, author = {{Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540603139}}, issn = {{0302-9743}}, title = {{{Shared memory simulations with triple-logarithmic delay}}}, doi = {{10.1007/3-540-60313-1_133}}, year = {{1995}}, } @inproceedings{16706, author = {{Meyer auf der Heide, Friedhelm and Storch, Martin and Wanka, Rolf}}, booktitle = {{Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures - SPAA '95}}, isbn = {{0897917170}}, title = {{{Optimal trade-offs between size and slowdown for universal parallel networks}}}, doi = {{10.1145/215399.215430}}, year = {{1995}}, } @inproceedings{16707, author = {{Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker}}, booktitle = {{Proceedings Third Israel Symposium on the Theory of Computing and Systems}}, isbn = {{0818669152}}, title = {{{Improved optimal shared memory simulations, and the power of reconfiguration}}}, doi = {{10.1109/istcs.1995.377051}}, year = {{1995}}, } @inbook{16717, author = {{Meyer auf der Heide, Friedhelm and Westermann, Matthias}}, booktitle = {{Graph-Theoretic Concepts in Computer Science}}, isbn = {{9783540606185}}, issn = {{0302-9743}}, title = {{{Hot-potato routing on multi-dimensional tori}}}, doi = {{10.1007/3-540-60618-1_77}}, year = {{1995}}, } @inbook{16874, author = {{Bäumker, Armin and Dittrich, Wolfgang and Meyer auf der Heide, Friedhelm}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540603139}}, issn = {{0302-9743}}, title = {{{Truly efficient parallel algorithms: c-optimal multisearch for an extension of the BSP model}}}, doi = {{10.1007/3-540-60313-1_131}}, year = {{1995}}, } @phdthesis{19624, author = {{Wanka, Rolf}}, title = {{{Paralleles Sortieren auf mehrdimensionalen Gittern}}}, year = {{1994}}, } @article{16728, author = {{Dietzfelbinger, Martin and Karlin, Anna and Mehlhorn, Kurt and Meyer auf der Heide, Friedhelm and Rohnert, Hans and Tarjan, Robert E.}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{738--761}}, title = {{{Dynamic Perfect Hashing: Upper and Lower Bounds}}}, doi = {{10.1137/s0097539791194094}}, year = {{1994}}, } @book{17477, editor = {{Meyer auf der Heide, Friedhelm and Monien, B. and Rosenberg, A. L.}}, isbn = {{9783540567318}}, issn = {{0302-9743}}, publisher = {{Springer}}, title = {{{Parallel Architectures and Their Efficient Use}}}, doi = {{10.1007/3-540-56731-3}}, year = {{1993}}, } @inproceedings{17479, author = {{Kastens, Uwe and Meyer auf der Heide, Friedhelm and Wachsmann, Alf and Wichmann, Friedrich}}, booktitle = {{Proc. 3rd PASA Workshop, PARS Mitteilungen}}, pages = {{50--55}}, title = {{{OCCAM-light: A Language Combining Shared Memory and Message Passing (A First Report)}}}, year = {{1993}}, } @article{16729, author = {{Dietzfelbinger, M. and Meyer auf der Heide, Friedhelm}}, issn = {{0890-5401}}, journal = {{Information and Computation}}, pages = {{196--217}}, title = {{{An Optimal Parallel Dictionary}}}, doi = {{10.1006/inco.1993.1007}}, year = {{1993}}, } @inbook{16730, author = {{Meyer auf der Heide, Friedhelm and Oesterdiekhoff, Brigitte and Wanka, Rolf}}, booktitle = {{Automata, Languages and Programming}}, isbn = {{9783540569398}}, issn = {{0302-9743}}, title = {{{Strongly adaptive token distribution}}}, doi = {{10.1007/3-540-56939-1_89}}, year = {{1993}}, } @inproceedings{16731, author = {{Dietzfelbinger, Martin and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures - SPAA '93}}, isbn = {{0897915992}}, title = {{{Simple, efficient shared memory simulations}}}, doi = {{10.1145/165231.165246}}, year = {{1993}}, } @inbook{16732, author = {{Lürwer-Brüggemeier, Katharina and Meyer auf der Heide, Friedhelm}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540565031}}, issn = {{0302-9743}}, title = {{{Capabilities and complexity of computations with integer division}}}, doi = {{10.1007/3-540-56503-5_46}}, year = {{1993}}, } @article{18936, abstract = {{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.}}, author = {{Kutylowski, Miroslaw and Wanka, Rolf}}, issn = {{0129-6264}}, journal = {{Parallel Processing Letters 2}}, pages = {{213--220}}, title = {{{Periodic Sorting on Two-Dimensional Meshes}}}, doi = {{10.1142/s0129626492000349}}, year = {{1992}}, } @inbook{16733, author = {{Dietzfelbinger, Martin and Meyer auf der Heide, Friedhelm}}, booktitle = {{Data structures and efficient algorithms}}, isbn = {{9783540554882}}, issn = {{0302-9743}}, title = {{{High performance universal hashing, with applications to shared memory simulations}}}, doi = {{10.1007/3-540-55488-2_31}}, year = {{1992}}, } @inbook{16734, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540567318}}, issn = {{0302-9743}}, title = {{{Hashing strategies for simulating shared memory on distributed memory machines}}}, doi = {{10.1007/3-540-56731-3_3}}, year = {{1992}}, } @inbook{16735, author = {{Meyer auf der Heide, Friedhelm and Pham, Hieu Thien}}, booktitle = {{STACS 92}}, isbn = {{9783540552109}}, issn = {{0302-9743}}, title = {{{On the performance of networks with multiple busses}}}, doi = {{10.1007/3-540-55210-3_176}}, year = {{1992}}, } @inproceedings{16736, author = {{Karp, Richard M. and Luby, Michael and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92}}, isbn = {{0897915119}}, title = {{{Efficient PRAM simulation on a distributed memory machine}}}, doi = {{10.1145/129712.129743}}, year = {{1992}}, } @inbook{16737, author = {{Dietzfelbinger, Martin and Meyer auf der Heide, Friedhelm}}, booktitle = {{TEUBNER-TEXTE zur Informatik}}, isbn = {{9783815420331}}, issn = {{1615-4584}}, title = {{{Dynamic Hashing in Real Time}}}, doi = {{10.1007/978-3-322-95233-2_7}}, year = {{1992}}, } @inbook{3050, author = {{Alt, Helmut and Blömer, Johannes and Wagener, Hubert}}, booktitle = {{Automata, Languages and Programming}}, isbn = {{3540528261}}, pages = {{703--716}}, publisher = {{Springer-Verlag}}, title = {{{Approximation of convex polygons}}}, doi = {{10.1007/bfb0032068}}, year = {{1990}}, } @inbook{16738, author = {{Dietzfelbinger, Martin and Meyer auf der Heide, Friedhelm}}, booktitle = {{Automata, Languages and Programming}}, isbn = {{3540528261}}, title = {{{A new universal class of hash functions and dynamic hashing in real time}}}, doi = {{10.1007/bfb0032018}}, year = {{1990}}, } @inbook{16739, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{3540529535}}, title = {{{Dynamic hashing strategies}}}, doi = {{10.1007/bfb0029597}}, year = {{1990}}, } @inbook{16740, author = {{Karpinski, Marek and Meyer auf der Heide, Friedhelm}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{3540529535}}, title = {{{On the complexity of genuinely polynomial computation}}}, doi = {{10.1007/bfb0029630}}, year = {{1990}}, } @inproceedings{16741, author = {{Dietzfelbinger, M. and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90}}, isbn = {{0897913612}}, title = {{{How to distribute a dictionary in a complete network}}}, doi = {{10.1145/100216.100229}}, year = {{1990}}, } @inproceedings{16742, author = {{Gil, J. and Meyer auf der Heide, Friedhelm and Wigderson, A.}}, booktitle = {{Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90}}, isbn = {{0897913612}}, title = {{{Not all keys can be hashed in constant time}}}, doi = {{10.1145/100216.100247}}, year = {{1990}}, } @article{16824, author = {{Meyer auf der Heide, Friedhelm}}, journal = {{Informatik Spektrum}}, number = {{4}}, pages = {{231--232}}, title = {{{Das Heinz Nixdorf-Institut der Universität-GH Paderborn}}}, volume = {{13}}, year = {{1990}}, } @article{16743, author = {{Just, Bettina and Meyer auf der Heide, Friedhelm and Wigderson, Avi}}, issn = {{0988-3754}}, journal = {{RAIRO - Theoretical Informatics and Applications}}, pages = {{101--111}}, title = {{{On computations with integer division}}}, doi = {{10.1051/ita/1989230101011}}, year = {{1989}}, } @inproceedings{16744, author = {{Dietzfelbinger, M. and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the first annual ACM symposium on Parallel algorithms and architectures - SPAA '89}}, isbn = {{089791323X}}, title = {{{An optimal parallel dictionary}}}, doi = {{10.1145/72935.72974}}, year = {{1989}}, } @inbook{16745, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{STACS 89}}, isbn = {{3540508406}}, title = {{{On genuinely time bounded computations}}}, doi = {{10.1007/bfb0028969}}, year = {{1989}}, } @inbook{16746, author = {{Meyer auf der Heide, Friedhelm and Wanka, Rolf}}, booktitle = {{STACS 89}}, isbn = {{3540508406}}, title = {{{Time-optimal simulations of networks by universal parallel computers}}}, doi = {{10.1007/bfb0028978}}, year = {{1989}}, } @inbook{16789, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{STACS 89}}, isbn = {{9783540508403}}, issn = {{0302-9743}}, title = {{{Computing minimum spanning forests on 1- and 2-dimensional processor arrays}}}, doi = {{10.1007/bfb0028983}}, year = {{1989}}, } @article{16763, author = {{Babai, László and Just, Bettina and Meyer auf der Heide, Friedhelm}}, issn = {{0890-5401}}, journal = {{Information and Computation}}, pages = {{99--107}}, title = {{{On the limits of computations with the floor function}}}, doi = {{10.1016/0890-5401(88)90031-4}}, year = {{1988}}, } @article{16764, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0004-5411}}, journal = {{Journal of the ACM (JACM)}}, pages = {{740--747}}, title = {{{Fast algorithms for N-dimensional restrictions of hard problems}}}, doi = {{10.1145/44483.44490}}, year = {{1988}}, } @article{16765, author = {{Borodin, Allan and Fich, Faith E. and Meyer auf der Heide, Friedhelm and Upfal, Eli and Wigderson, Avi}}, issn = {{0304-3975}}, journal = {{Theoretical Computer Science}}, pages = {{57--68}}, title = {{{A tradeoff between search and update time for the implicit dictionary problem}}}, doi = {{10.1016/0304-3975(88)90018-7}}, year = {{1988}}, } @inproceedings{16766, author = {{Dietzfelbinger, M. and Karlin, A. and Mehlhorn, K. and Meyer auf der Heide, Friedhelm and Rohnert, H. and Tarjan, R.E.}}, booktitle = {{[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science}}, isbn = {{0818608773}}, title = {{{Dynamic perfect hashing: upper and lower bounds}}}, doi = {{10.1109/sfcs.1988.21968}}, year = {{1988}}, } @inbook{16767, author = {{Just, Bettina and Mathematik, Fb and Meyer auf der Heide, Friedhelm and Informatik, Fb and Wigderson, Avi}}, booktitle = {{STACS 88}}, isbn = {{9783540188346}}, issn = {{0302-9743}}, title = {{{On computations with integer division}}}, doi = {{10.1007/bfb0035829}}, year = {{1988}}, } @inbook{16768, author = {{Dietzfelbinger, M. and Mehlhorn, K. and Meyer auf der Heide, Friedhelm and Rohnert, H.}}, booktitle = {{SWAT 88}}, isbn = {{9783540194873}}, issn = {{0302-9743}}, title = {{{Upper and lower bounds for the dictionary problem}}}, doi = {{10.1007/3-540-19487-8_24}}, year = {{1988}}, } @article{16772, author = {{Borodin, A. and Fich, F. and Meyer auf der Heide, Friedhelm and Upfal, E. and Wigderson, A.}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{97--99}}, title = {{{A Time-Space Tradeoff for Element Distinctness}}}, doi = {{10.1137/0216007}}, year = {{1987}}, } @article{16773, author = {{Meyer auf der Heide, Friedhelm and Wigderson, Avi}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{100--107}}, title = {{{The Complexity of Parallel Sorting}}}, doi = {{10.1137/0216008}}, year = {{1987}}, } @article{16771, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{106--119}}, title = {{{Efficient Simulations among Several Models of Parallel Computers}}}, doi = {{10.1137/0215008}}, year = {{1986}}, } @inbook{16774, author = {{Borodin, Allan and Fich, Faith E. and Meyer auf der Heide, Friedhelm and Upfal, Eli and Wigderson, Avi}}, booktitle = {{Automata, Languages and Programming}}, isbn = {{9783540167617}}, issn = {{0302-9743}}, title = {{{A tradeoff between search and update time for the implicit dictionary problem}}}, doi = {{10.1007/3-540-16761-7_54}}, year = {{1986}}, } @inbook{16775, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{STACS 86}}, isbn = {{9783540160786}}, issn = {{0302-9743}}, title = {{{Speeding up random access machines by few processors}}}, doi = {{10.1007/3-540-16078-7_72}}, year = {{1986}}, } @inbook{16776, author = {{Borodin, A. and Fich, F. and Meyer auf der Heide, Friedhelm and Upfal, E. and Wigderson, A.}}, booktitle = {{STACS 86}}, isbn = {{9783540160786}}, issn = {{0302-9743}}, title = {{{A time-space tradeoff for element distinctness}}}, doi = {{10.1007/3-540-16078-7_89}}, year = {{1986}}, } @article{16779, author = {{Lautemann, Clemens and Meyer auf der Heide, Friedhelm}}, issn = {{0020-0190}}, journal = {{Information Processing Letters}}, pages = {{101--105}}, title = {{{Lower time bounds for integer programming with two variables}}}, doi = {{10.1016/0020-0190(85)90042-0}}, year = {{1985}}, } @article{16780, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0004-5411}}, journal = {{Journal of the ACM (JACM)}}, pages = {{929--937}}, title = {{{Lower bounds for solving linear diophantine equations on random access machines}}}, doi = {{10.1145/4221.4250}}, year = {{1985}}, } @article{16781, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0304-3975}}, journal = {{Theoretical Computer Science}}, pages = {{325--330}}, title = {{{Simulating probabilistic by deterministic algebraic computation trees}}}, doi = {{10.1016/0304-3975(85)90079-9}}, year = {{1985}}, } @inproceedings{16782, author = {{Meyer auf der Heide, Friedhelm and Wigderson, Avi}}, booktitle = {{26th Annual Symposium on Foundations of Computer Science (sfcs 1985)}}, isbn = {{0818606444}}, title = {{{The complexity of parallel sorting}}}, doi = {{10.1109/sfcs.1985.58}}, year = {{1985}}, } @inproceedings{16783, author = {{Fich, F E and Meyer auf der Heide, Friedhelm and Ragde, P and Wigderson, A}}, booktitle = {{Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85}}, isbn = {{0897911512}}, title = {{{One, two, three . . . infinity: lower bounds for parallel computation}}}, doi = {{10.1145/22145.22151}}, year = {{1985}}, } @inproceedings{16784, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85}}, isbn = {{0897911512}}, title = {{{Fast algorithms for n-dimensional restrictions of hard problems}}}, doi = {{10.1145/22145.22191}}, year = {{1985}}, } @inproceedings{16788, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{26th Annual Symposium on Foundations of Computer Science (sfcs 1985)}}, isbn = {{0818606444}}, title = {{{Nondeterministic versus probabilistic linear search algorithms}}}, doi = {{10.1109/sfcs.1985.38}}, year = {{1985}}, } @article{16823, author = {{Meyer auf der Heide, Friedhelm}}, journal = {{Information and Control}}, number = {{1-3}}, pages = {{195--211}}, title = {{{Lower time bounds for solving linear diophantine equations on several parallel computational models}}}, doi = {{10.1016/S0019-9958(85)80035-8}}, volume = {{67}}, year = {{1985}}, } @article{16785, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0004-5411}}, journal = {{Journal of the ACM (JACM)}}, pages = {{668--676}}, title = {{{A Polynomial Linear Search Algorithm forr the n-Dimensional Knapsack Problem}}}, doi = {{10.1145/828.322450}}, year = {{1984}}, } @inproceedings{16786, author = {{Meyer auf der Heide, Friedhelm and Reischuk, R.}}, booktitle = {{25th Annual Symposium onFoundations of Computer Science, 1984.}}, isbn = {{081860591X}}, title = {{{On The Limits To Speed Up Parallel Machines By Large Hardware And Unbounded Communication}}}, doi = {{10.1109/sfcs.1984.715901}}, year = {{1984}}, } @inbook{16787, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{STACS 84}}, isbn = {{9783540129202}}, issn = {{0302-9743}}, title = {{{Efficient simulations among several models of parallel computers (extended abstract)}}}, doi = {{10.1007/3-540-12920-0_20}}, year = {{1984}}, } @article{16806, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0001-5903}}, journal = {{Acta Informatica}}, pages = {{269--296}}, title = {{{Efficiency of universal parallel computers}}}, doi = {{10.1007/bf00265559}}, year = {{1983}}, } @article{16807, author = {{Klein, Peter and Meyer auf der Heide, Friedhelm}}, issn = {{0001-5903}}, journal = {{Acta Informatica}}, pages = {{385--395}}, title = {{{A lower time bound for the knapsack problem on random access machines}}}, doi = {{10.1007/bf00290735}}, year = {{1983}}, } @article{16808, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0020-0190}}, journal = {{Information Processing Letters}}, pages = {{1--2}}, title = {{{Infinite cube-connected cycles}}}, doi = {{10.1016/0020-0190(83)90001-7}}, year = {{1983}}, } @inproceedings{16809, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83}}, isbn = {{0897910990}}, title = {{{A polynomial linear search algorithm for the n-dimensional knapsack problem}}}, doi = {{10.1145/800061.808734}}, year = {{1983}}, } @inbook{16810, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{3540119736}}, title = {{{Efficiency of universal parallel computers}}}, doi = {{10.1007/bfb0036483}}, year = {{1983}}, } @inbook{16813, author = {{Meyer auf der Heide, Friedhelm and Rollik, Anton}}, booktitle = {{Fundamentals of Computation Theory}}, isbn = {{9783540108542}}, issn = {{0302-9743}}, title = {{{Random access machines and straight-line programs}}}, doi = {{10.1007/3-540-10854-8_29}}, year = {{1981}}, } @inbook{16814, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540108566}}, issn = {{0302-9743}}, title = {{{Time-processor trade-offs for universal parallel computers}}}, doi = {{10.1007/3-540-10856-4_111}}, year = {{1981}}, } @article{16820, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0304-3975}}, journal = {{Theoretical Computer Science}}, pages = {{315--322}}, title = {{{A comparison of two variations of a pebble game on graphs}}}, doi = {{10.1016/s0304-3975(81)80004-7}}, year = {{1981}}, } @inbook{16815, author = {{Klein, P. and Meyer auf der Heide, Friedhelm}}, booktitle = {{GI - 10. Jahrestagung}}, isbn = {{9783540103882}}, issn = {{0343-3005}}, title = {{{Untere Zeitschranken für das Rucksack-Problem}}}, doi = {{10.1007/978-3-642-67838-7_34}}, year = {{1980}}, } @article{16812, author = {{Meyer auf der Heide, Friedhelm}}, journal = {{Automata, Languages and Programming. ICALP 1979}}, pages = {{411--421}}, title = {{{A comparison of two variations of a pebble game on graphs}}}, doi = {{10.1007/3-540-09510-1_32 }}, year = {{1979}}, }