@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}}, }