×

Dietzfelbinger, Martin

Author ID: dietzfelbinger.martin Recent zbMATH articles by "Dietzfelbinger, Martin"
Published as: Dietzfelbinger, Martin; Dietzfelbinger, M.

Publications by Year

Citations contained in zbMATH Open

56 Publications have been cited 365 times in 262 Documents Cited by Year
Dynamic perfect hashing: Upper and lower bounds. Zbl 0820.68038
Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E.
50
1994
Tight thresholds for Cuckoo hashing via XORSAT (extended abstract). Zbl 1256.68047
Dietzfelbinger, Martin; Goerdt, Andreas; Mitzenmacher, Michael; Montanari, Andrea; Pagh, Rasmus; Rink, Michael
38
2010
A reliable randomized algorithm for the closest-pair problem. Zbl 0888.68061
Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti
29
1997
A new universal class of hash functions and dynamic hashing in real time. Zbl 0765.68026
Dietzfelbinger, Martin; Meyer auf der Heide, Friedhelm
25
1990
Balanced allocation and dictionaries with tightly packed constant size bins. Zbl 1115.68169
Dietzfelbinger, Martin; Weidling, Christoph
23
2007
A comparison of two lower-bound methods for communication complexity. Zbl 0874.68150
Dietzfelbinger, Martin; Hromkovič, Juraj; Schnitger, Georg
18
1996
Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes. Zbl 1379.68104
Dietzfelbinger, Martin
15
1996
Exact lower time bounds for computing Boolean functions on CREW PRAMs. Zbl 0822.68049
Dietzfelbinger, Martin; Kutyłowski, Mirosław; Reischuk, Rüdiger
14
1994
Succinct data structures for retrieval and approximate membership (extended abstract). Zbl 1153.68364
Dietzfelbinger, Martin; Pagh, Rasmus
13
2008
Almost random graphs with simple hash functions. Zbl 1192.68227
Dietzfelbinger, Martin; Woelfel, Philipp
10
2003
Explicit and efficient hash families suffice for cuckoo hashing with a stash. Zbl 1314.68106
Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp
9
2014
Polynomial hash functions are reliable (extended abstract). Zbl 1425.68098
Dietzfelbinger, M.; Gil, J.; Matias, Y.; Pippenger, N.
8
1992
Hash, displace, and compress. Zbl 1256.68046
Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin
7
2009
Sequential and parallel algorithms and data structures. The basic toolbox. Zbl 1445.68003
Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman
6
2019
Primality testing in polynomial time. From randomized algorithms to “PRIMES is in P”. Zbl 1058.11070
Dietzfelbinger, Martin
5
2004
An optimal parallel dictionary. Zbl 0786.68023
Dietzfelbinger, Martin; Meyer auf der Heide, Friedhelm
5
1993
Applications of a splitting trick. Zbl 1248.68166
Dietzfelbinger, Martin; Rink, Michael
5
2009
Tight bounds for blind search on the integers and the reals. Zbl 1261.68069
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
5
2010
The speed of copying on one-tape off-line turing machines. Zbl 0682.68043
Dietzfelbinger, Martin
4
1989
The linear-array problem in communication complexity resolved. Zbl 0974.68011
Dietzfelbinger, Martin
4
1999
Linear hash functions. Zbl 1065.68520
Alon, Noga; Dietzfelbinger, Martin; Miltersen, Peter Bro; Petrank, Erez; Tardos, Gábor
4
1999
Precision, local search and unimodal functions. Zbl 1211.68520
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
3
2011
A characterization of average case communication complexity. Zbl 1184.68251
Dietzfelbinger, Martin; Wunderlich, Henning
3
2007
Balanced allocation and dictionaries with tightly packed constant size bins. Zbl 1082.68557
Dietzfelbinger, Martin; Weidling, Christoph
3
2005
Weaknesses of cuckoo hashing with a simple universal hash class: The case of large universes. Zbl 1206.68101
Dietzfelbinger, Martin; Schellbach, Ulf
3
2009
The complexity of matrix transposition on one-tape off-line Turing machines. Zbl 0731.68042
Dietzfelbinger, Martin; Maass, Wolfgang; Schnitger, Georg
3
1991
On testing single connectedness in directed graphs and some related problems. Zbl 1329.05128
Dietzfelbinger, Martin; Jaberi, Raed
3
2015
On risks of using cuckoo hashing with simple universal hash classes. Zbl 1421.68024
Dietzfelbinger, Martin; Schellbach, Ulf
3
2009
Optimal partitioning for dual pivot quicksort (extended abstract). Zbl 1336.68051
Aumüller, Martin; Dietzfelbinger, Martin
3
2013
A perfect parallel dictionary. Zbl 1493.68134
Bast, Holger; Dietzfelbinger, Martin; Hagerup, Torben
3
1992
Tight bounds for blind search on the integers. Zbl 1259.68151
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
3
2008
How good is multi-pivot quicksort? Zbl 1430.68061
Aumüller, Martin; Dietzfelbinger, Martin; Klaue, Pascal
3
2016
Lower bounds for sorting of sums. Zbl 0686.68034
Dietzfelbinger, Martin
2
1989
Cuckoo hashing with pages. Zbl 1256.68048
Dietzfelbinger, Martin; Mitzenmacher, Michael; Rink, Michael
2
2011
Explicit and efficient hash families suffice for cuckoo hashing with a stash. Zbl 1365.68168
Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp
2
2012
Feasible time-optimal algorithms for Boolean functions on exclusive-write parallel random-access machines. Zbl 0864.68037
Dietzfelbinger, Martin; Kutyłowski, Mirosław; Reischuk, Rüdiger
2
1996
The complexity of matrix transposition on one-tape off-line Turing machines with output tape. Zbl 0783.68054
Dietzfelbinger, Martin; Maass, Wolfgang
2
1993
The probability of a rendezvous is minimal in complete graphs. Zbl 1019.68074
Dietzfelbinger, Martin
2
2002
Counting zeros in random walks on the integers and analysis of optimal dual-pivot quicksort. Zbl 1411.68042
Aumüller, Martin; Dietzfelbinger, Martin; Heuberger, Clemens; Krenn, Daniel; Prodinger, Helmut
2
2016
Dense peelable random uniform hypergraphs. Zbl 07525475
Dietzfelbinger, Martin; Walzer, Stefan
2
2019
Constant-time retrieval with \(O(\log m)\) extra bits. Zbl 07559133
Dietzfelbinger, Martin; Walzer, Stefan
2
2019
Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths. Zbl 1432.68108
Aumüller, Martin; Dietzfelbinger, Martin; Heuberger, Clemens; Krenn, Daniel; Prodinger, Helmut
2
2019
Optimal partitioning for dual-pivot quicksort. Zbl 1398.68114
Aumüller, Martin; Dietzfelbinger, Martin
2
2016
Upper and lower bounds for the dictionary problem. Zbl 0651.68095
Dietzfelbinger, M.; Mehlhorn, K.; Meyer auf der Heide, F.; Rohnert, H.
1
1988
Lower bound arguments with “inaccessible” numbers. Zbl 0652.68039
Dietzfelbinger, Martin; Maass, Wolfgang
1
1988
Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape. Zbl 0962.68066
Dietzfelbinger, Martin; Hühne, Martin
1
1999
Is linear hashing good? Zbl 0963.68044
Alon, Noga; Dietzfelbinger, Martin; Miltersen, Peter Bro; Petrank, Erez; Tardos, Gábor
1
1999
Gossiping and broadcasting versus computing functions in networks. Zbl 1062.68018
Dietzfelbinger, Martin
1
2004
Design strategies for minimal perfect hash functions. Zbl 1175.68556
Dietzfelbinger, Martin
1
2007
Two lower bound arguments with ”inaccessible” numbers. Zbl 0611.68022
Dietzfelbinger, Martin; Maass, Wolfgang
1
1986
On the probability of rendezvous in graphs. Zbl 1106.68079
Dietzfelbinger, Martin; Tamaki, Hisao
1
2005
Pocket bock of algorithms. (Taschenbuch der Algorithmen.) Zbl 1138.68669
1
2008
Tight lower bounds for greedy routing in uniform small world rings. Zbl 1304.68014
Dietzfelbinger, Martin; Woelfel, Philipp
1
2009
Universal hashing via integer arithmetic without primes, revisited. Zbl 1514.68043
Dietzfelbinger, Martin
1
2018
Algorithms unplugged. Zbl 1206.68024
1
2011
A subquadratic algorithm for 3XOR. Zbl 1512.68437
Dietzfelbinger, Martin; Schlag, Philipp; Walzer, Stefan
1
2018
Sequential and parallel algorithms and data structures. The basic toolbox. Zbl 1445.68003
Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman
6
2019
Dense peelable random uniform hypergraphs. Zbl 07525475
Dietzfelbinger, Martin; Walzer, Stefan
2
2019
Constant-time retrieval with \(O(\log m)\) extra bits. Zbl 07559133
Dietzfelbinger, Martin; Walzer, Stefan
2
2019
Dual-pivot quicksort: optimality, analysis and zeros of associated lattice paths. Zbl 1432.68108
Aumüller, Martin; Dietzfelbinger, Martin; Heuberger, Clemens; Krenn, Daniel; Prodinger, Helmut
2
2019
Universal hashing via integer arithmetic without primes, revisited. Zbl 1514.68043
Dietzfelbinger, Martin
1
2018
A subquadratic algorithm for 3XOR. Zbl 1512.68437
Dietzfelbinger, Martin; Schlag, Philipp; Walzer, Stefan
1
2018
How good is multi-pivot quicksort? Zbl 1430.68061
Aumüller, Martin; Dietzfelbinger, Martin; Klaue, Pascal
3
2016
Counting zeros in random walks on the integers and analysis of optimal dual-pivot quicksort. Zbl 1411.68042
Aumüller, Martin; Dietzfelbinger, Martin; Heuberger, Clemens; Krenn, Daniel; Prodinger, Helmut
2
2016
Optimal partitioning for dual-pivot quicksort. Zbl 1398.68114
Aumüller, Martin; Dietzfelbinger, Martin
2
2016
On testing single connectedness in directed graphs and some related problems. Zbl 1329.05128
Dietzfelbinger, Martin; Jaberi, Raed
3
2015
Explicit and efficient hash families suffice for cuckoo hashing with a stash. Zbl 1314.68106
Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp
9
2014
Optimal partitioning for dual pivot quicksort (extended abstract). Zbl 1336.68051
Aumüller, Martin; Dietzfelbinger, Martin
3
2013
Explicit and efficient hash families suffice for cuckoo hashing with a stash. Zbl 1365.68168
Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp
2
2012
Precision, local search and unimodal functions. Zbl 1211.68520
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
3
2011
Cuckoo hashing with pages. Zbl 1256.68048
Dietzfelbinger, Martin; Mitzenmacher, Michael; Rink, Michael
2
2011
Algorithms unplugged. Zbl 1206.68024
1
2011
Tight thresholds for Cuckoo hashing via XORSAT (extended abstract). Zbl 1256.68047
Dietzfelbinger, Martin; Goerdt, Andreas; Mitzenmacher, Michael; Montanari, Andrea; Pagh, Rasmus; Rink, Michael
38
2010
Tight bounds for blind search on the integers and the reals. Zbl 1261.68069
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
5
2010
Hash, displace, and compress. Zbl 1256.68046
Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin
7
2009
Applications of a splitting trick. Zbl 1248.68166
Dietzfelbinger, Martin; Rink, Michael
5
2009
Weaknesses of cuckoo hashing with a simple universal hash class: The case of large universes. Zbl 1206.68101
Dietzfelbinger, Martin; Schellbach, Ulf
3
2009
On risks of using cuckoo hashing with simple universal hash classes. Zbl 1421.68024
Dietzfelbinger, Martin; Schellbach, Ulf
3
2009
Tight lower bounds for greedy routing in uniform small world rings. Zbl 1304.68014
Dietzfelbinger, Martin; Woelfel, Philipp
1
2009
Succinct data structures for retrieval and approximate membership (extended abstract). Zbl 1153.68364
Dietzfelbinger, Martin; Pagh, Rasmus
13
2008
Tight bounds for blind search on the integers. Zbl 1259.68151
Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp
3
2008
Pocket bock of algorithms. (Taschenbuch der Algorithmen.) Zbl 1138.68669
1
2008
Balanced allocation and dictionaries with tightly packed constant size bins. Zbl 1115.68169
Dietzfelbinger, Martin; Weidling, Christoph
23
2007
A characterization of average case communication complexity. Zbl 1184.68251
Dietzfelbinger, Martin; Wunderlich, Henning
3
2007
Design strategies for minimal perfect hash functions. Zbl 1175.68556
Dietzfelbinger, Martin
1
2007
Balanced allocation and dictionaries with tightly packed constant size bins. Zbl 1082.68557
Dietzfelbinger, Martin; Weidling, Christoph
3
2005
On the probability of rendezvous in graphs. Zbl 1106.68079
Dietzfelbinger, Martin; Tamaki, Hisao
1
2005
Primality testing in polynomial time. From randomized algorithms to “PRIMES is in P”. Zbl 1058.11070
Dietzfelbinger, Martin
5
2004
Gossiping and broadcasting versus computing functions in networks. Zbl 1062.68018
Dietzfelbinger, Martin
1
2004
Almost random graphs with simple hash functions. Zbl 1192.68227
Dietzfelbinger, Martin; Woelfel, Philipp
10
2003
The probability of a rendezvous is minimal in complete graphs. Zbl 1019.68074
Dietzfelbinger, Martin
2
2002
The linear-array problem in communication complexity resolved. Zbl 0974.68011
Dietzfelbinger, Martin
4
1999
Linear hash functions. Zbl 1065.68520
Alon, Noga; Dietzfelbinger, Martin; Miltersen, Peter Bro; Petrank, Erez; Tardos, Gábor
4
1999
Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape. Zbl 0962.68066
Dietzfelbinger, Martin; Hühne, Martin
1
1999
Is linear hashing good? Zbl 0963.68044
Alon, Noga; Dietzfelbinger, Martin; Miltersen, Peter Bro; Petrank, Erez; Tardos, Gábor
1
1999
A reliable randomized algorithm for the closest-pair problem. Zbl 0888.68061
Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti
29
1997
A comparison of two lower-bound methods for communication complexity. Zbl 0874.68150
Dietzfelbinger, Martin; Hromkovič, Juraj; Schnitger, Georg
18
1996
Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes. Zbl 1379.68104
Dietzfelbinger, Martin
15
1996
Feasible time-optimal algorithms for Boolean functions on exclusive-write parallel random-access machines. Zbl 0864.68037
Dietzfelbinger, Martin; Kutyłowski, Mirosław; Reischuk, Rüdiger
2
1996
Dynamic perfect hashing: Upper and lower bounds. Zbl 0820.68038
Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E.
50
1994
Exact lower time bounds for computing Boolean functions on CREW PRAMs. Zbl 0822.68049
Dietzfelbinger, Martin; Kutyłowski, Mirosław; Reischuk, Rüdiger
14
1994
An optimal parallel dictionary. Zbl 0786.68023
Dietzfelbinger, Martin; Meyer auf der Heide, Friedhelm
5
1993
The complexity of matrix transposition on one-tape off-line Turing machines with output tape. Zbl 0783.68054
Dietzfelbinger, Martin; Maass, Wolfgang
2
1993
Polynomial hash functions are reliable (extended abstract). Zbl 1425.68098
Dietzfelbinger, M.; Gil, J.; Matias, Y.; Pippenger, N.
8
1992
A perfect parallel dictionary. Zbl 1493.68134
Bast, Holger; Dietzfelbinger, Martin; Hagerup, Torben
3
1992
The complexity of matrix transposition on one-tape off-line Turing machines. Zbl 0731.68042
Dietzfelbinger, Martin; Maass, Wolfgang; Schnitger, Georg
3
1991
A new universal class of hash functions and dynamic hashing in real time. Zbl 0765.68026
Dietzfelbinger, Martin; Meyer auf der Heide, Friedhelm
25
1990
The speed of copying on one-tape off-line turing machines. Zbl 0682.68043
Dietzfelbinger, Martin
4
1989
Lower bounds for sorting of sums. Zbl 0686.68034
Dietzfelbinger, Martin
2
1989
Upper and lower bounds for the dictionary problem. Zbl 0651.68095
Dietzfelbinger, M.; Mehlhorn, K.; Meyer auf der Heide, F.; Rohnert, H.
1
1988
Lower bound arguments with “inaccessible” numbers. Zbl 0652.68039
Dietzfelbinger, Martin; Maass, Wolfgang
1
1988
Two lower bound arguments with ”inaccessible” numbers. Zbl 0611.68022
Dietzfelbinger, Martin; Maass, Wolfgang
1
1986
all top 5

Cited by 476 Authors

21 Dietzfelbinger, Martin
10 Schnitger, Georg
9 Hromkovič, Juraj
7 Naor, Moni
7 Walzer, Stefan
6 Coja-Oghlan, Amin
5 Matias, Yossi
5 Theis, Dirk Oliver
5 Woelfel, Philipp
4 Bercea, Ioana Oriana
4 Even, Guy
4 Fich, Faith Ellen
4 Gawrychowski, Paweł
4 Maass, Wolfgang
4 Meyer auf der Heide, Friedhelm
4 Mitzenmacher, Michael
4 Müller, Noela S.
3 Belazzougui, Djamal
3 Czech, Zbigniew J.
3 Doerr, Benjamin
3 Frieze, Alan Michael
3 Gao, Pu
3 Hagerup, Torben
3 Han, Yijie
3 Havas, George
3 Knudsen, Mathias Bæk Tejs
3 Kociumaka, Tomasz
3 Lemire, Daniel
3 Majewski, Bohdan S.
3 Muluk, Komal
3 Porat, Ely
3 Pourmoradnasseri, Mozhgan
3 Sanders, Peter
3 Shraibman, Adi
3 Stemann, Volker
2 Achlioptas, Dimitris
2 Amano, Kazuyuki
2 Asharov, Gilad
2 Aumüller, Martin
2 Beame, Paul W.
2 Bille, Philip
2 Braverman, Mark
2 Chan, Hing-Lun
2 Chan, Timothy Moon-Yew
2 Chaudhuri, Shiva P.
2 Czumaj, Artur
2 Das, Avinandan
2 Devroye, Luc P. J. A.
2 Dinitz, Yefim
2 Doerr, Carola
2 Dubhashi, Devdatt P.
2 Edelkamp, Stefan
2 Fountoulakis, Nikolaos
2 Gibbons, Phillip B.
2 Gil, Joseph
2 Gørtz, Inge Li
2 Ibrahimi, Morteza
2 Iliopoulos, Costas S.
2 Jeż, Artur
2 Kanesh, Lawqueen
2 Khosla, Megha
2 Kötzing, Timo
2 Kowaluk, Mirosław
2 Kraning, Matt
2 Kutyłowski, Mirosław
2 Lee, Troy
2 Lelarge, Marc
2 Lewenstein, Moshe
2 Li, Jian
2 Loryś, Krzysztof
2 Madathil, Jayakrishnan
2 Maier, Tobias
2 Malalla, Ebrahim
2 Martínez, Conrado
2 Mehlhorn, Kurt
2 Minaud, Brice
2 Montanari, Andrea
2 Morin, Pat
2 Mueller Graf, Thomas
2 Munro, J. Ian
2 Nebel, Markus E.
2 Norrish, Michael
2 Panagiotou, Konstantinos D.
2 Papamanthou, Charalampos
2 Pissis, Solon P.
2 Pontarelli, Salvatore
2 Pritchard, Paul A.
2 Purohit, Nidhi
2 Radoszewski, Jakub
2 Ragde, Prabhakar L.
2 Ramachandran, Vijaya
2 Reviriego, Pedro
2 Sach, Benjamin
2 Saurabh, Saket
2 Segev, Gil
2 Shahaf, Ido
2 Sly, Allan
2 Thorup, Mikkel
2 Vildhøj, Hjalte Wedel
2 Viola, Emanuele
...and 376 more Authors
all top 5

Cited in 61 Serials

30 Theoretical Computer Science
26 Algorithmica
20 Information Processing Letters
11 Information and Computation
7 Journal of Computer and System Sciences
6 SIAM Journal on Computing
6 Random Structures & Algorithms
5 Discrete Applied Mathematics
5 Combinatorics, Probability and Computing
5 ACM Journal of Experimental Algorithmics
4 Journal of Cryptology
4 Theory of Computing Systems
4 Journal of Discrete Algorithms
3 Computational Geometry
3 International Journal of Foundations of Computer Science
3 Computational Complexity
2 Israel Journal of Mathematics
2 Information Sciences
2 Combinatorica
2 The Annals of Applied Probability
2 Linear Algebra and its Applications
2 Distributed Computing
2 ACM Transactions on Algorithms
1 Communications in Mathematical Physics
1 Discrete Mathematics
1 The Mathematical Intelligencer
1 Acta Mathematica
1 Automatica
1 Journal of Combinatorial Theory. Series B
1 Mathematics of Operations Research
1 Networks
1 Quaestiones Mathematicae
1 European Journal of Combinatorics
1 Science of Computer Programming
1 Probability Theory and Related Fields
1 Discrete & Computational Geometry
1 Journal of Automated Reasoning
1 Journal of Parallel and Distributed Computing
1 International Journal of Computational Geometry & Applications
1 Computational Mathematics and Mathematical Physics
1 International Journal of Computer Mathematics
1 SIAM Review
1 Journal of the Egyptian Mathematical Society
1 The Electronic Journal of Combinatorics
1 Monte Carlo Methods and Applications
1 Parallel Algorithms and Applications
1 Journal of Combinatorial Optimization
1 Journal of Integer Sequences
1 Annals of Mathematics. Second Series
1 RAIRO. Theoretical Informatics and Applications
1 JMMA. Journal of Mathematical Modelling and Algorithms
1 Quantum Information Processing
1 Oberwolfach Reports
1 Mathematics in Computer Science
1 Journal of Mathematical Cryptology
1 Groups, Complexity, Cryptology
1 Algorithms
1 LIPIcs – Leibniz International Proceedings in Informatics
1 Statistics and Computing
1 Stochastic Systems
1 Journal of Mathematical Modelling and Algorithms in Operations Research

Citations by Year