Martin Dietzfelbinger

According to our database, Martin Dietzfelbinger authored at least 89 papers between 1986 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

On Hashing by (Random) Equations (Invited Talk).

Martin Dietzfelbinger

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2019

Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths.

Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger, Daniel Krenn, Helmut Prodinger

Comb. Probab. Comput., 2019

Constant-Time Retrieval with O(log m) Extra Bits.

Martin Dietzfelbinger, Stefan Walzer

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Efficient Gauss Elimination for Near-Quadratic Matrices with One Short Random Block per Row, with Applications.

Martin Dietzfelbinger, Stefan Walzer

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Dense Peelable Random Uniform Hypergraphs.

Martin Dietzfelbinger, Stefan Walzer

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Determining Minimum Hash Width for Hash Chains.

Martin Dietzfelbinger, Jörg Keller

Proceedings of the Third Central European Cybersecurity Conference, 2019

Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox

Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, Roman Dementiev

Springer, ISBN: 978-3-030-25208-3, 2019

2018

A Subquadratic Algorithm for 3XOR.

Martin Dietzfelbinger, Philipp Schlag, Stefan Walzer

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Universal Hashing via Integer Arithmetic Without Primes, Revisited.

Martin Dietzfelbinger

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

Special issue for the 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014, Budapest, Hungary.

Martin Dietzfelbinger

Inf. Comput., 2017

Theory and Applications of Hashing (Dagstuhl Seminar 17181).

Martin Dietzfelbinger, Michael Mitzenmacher, Rasmus Pagh, David P. Woodruff, Martin Aumüller

Dagstuhl Reports, 2017

2016

How Good Is Multi-Pivot Quicksort?

Martin Aumüller, Martin Dietzfelbinger, Pascal Klaue

ACM Trans. Algorithms, 2016

Optimal Partitioning for Dual-Pivot Quicksort.

Martin Aumüller, Martin Dietzfelbinger

ACM Trans. Algorithms, 2016

Preface of STACS 2013 Special Issue.

Anca Muscholl, Martin Dietzfelbinger

Theory Comput. Syst., 2016

A Simple Hash Class with Strong Randomness Properties in Graphs and Hypergraphs.

Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel

CoRR, 2016

Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort.

Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger, Daniel Krenn, Helmut Prodinger

CoRR, 2016

2015

Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs.

Martin Dietzfelbinger, Michael Rink

Theory Comput. Syst., 2015

On testing single connectedness in directed graphs and some related problems.

Martin Dietzfelbinger, Raed Jaberi

Inf. Process. Lett., 2015

2014

Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash.

Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel

Algorithmica, 2014

Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids.

Martin Dietzfelbinger, Philipp Woelfel

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Algorithmen und Datenstrukturen - die Grundwerkzeuge.

Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders

eXamen.press, Springer, ISBN: 978-3-642-05471-6, 2014

2013

Optimal Partitioning for Dual Pivot Quicksort - (Extended Abstract).

Martin Aumüller, Martin Dietzfelbinger

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs.

Martin Dietzfelbinger, Hendrik Peilke, Michael Rink

Proceedings of the Experimental Algorithms - 11th International Symposium, 2012

On Randomness in Hash Functions (Invited Talk).

Martin Dietzfelbinger

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

2011

Precision, Local Search and Unimodal Functions.

Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel

Algorithmica, 2011

Cuckoo Hashing with Pages.

Martin Dietzfelbinger, Michael Mitzenmacher, Michael Rink

Proceedings of the Algorithms - ESA 2011, 2011

Fingerprinting.

Martin Dietzfelbinger

Proceedings of the Algorithms Unplugged, 2011

2010

Ingo Wegener: seine Bücher.

Martin Dietzfelbinger

Inform. Spektrum, 2010

Tight Bounds for Blind Search on the Integers and the Reals.

Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel

Comb. Probab. Comput., 2010

Tight Thresholds for Cuckoo Hashing via XORSAT.

Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

In memoriam Prof. Dr. math. Ingo Wegener, 1950-2008.

Martin Dietzfelbinger

Theor. Comput. Sci., 2009

Tight lower bounds for greedy routing in uniform small world rings.

Martin Dietzfelbinger, Philipp Woelfel

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes.

Martin Dietzfelbinger, Ulf Schellbach

Proceedings of the SOFSEM 2009: Theory and Practice of Computer Science, 2009

On risks of using cuckoo hashing with simple universal hash classes.

Martin Dietzfelbinger, Ulf Schellbach

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Brief announcement: tight lower bounds for greedy routing in uniform small world rings.

Martin Dietzfelbinger, Philipp Woelfel

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

Perfect Hashing for State Spaces in BDD Representation.

Martin Dietzfelbinger, Stefan Edelkamp

Proceedings of the KI 2009: Advances in Artificial Intelligence, 2009

Applications of a Splitting Trick.

Martin Dietzfelbinger, Michael Rink

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Hash, Displace, and Compress.

Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger

Proceedings of the Algorithms, 2009

Experimental Variations of a Theoretically Good Retrieval Data Structure.

Martin Aumüller, Martin Dietzfelbinger, Michael Rink

Proceedings of the Algorithms, 2009

2008

Fingerprinting.

Martin Dietzfelbinger

Proceedings of the Taschenbuch der Algorithmen, 2008

A dictionary implementation based on dynamic perfect hashing.

Martin Dietzfelbinger, Martin Hühne, Christoph Weidling

ACM J. Exp. Algorithmics, 2008

Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, Algorithms, McGraw Hill, Boston (2007) ISBN 978-007352340-8, Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson/Addison Wesley, Boston (2006) ISBN 978-032129535-4.

Martin Dietzfelbinger

Comput. Sci. Rev., 2008

Succinct Data Structures for Retrieval and Approximate Membership

Martin Dietzfelbinger, Rasmus Pagh

CoRR, 2008

Tight Bounds for Blind Search on the Integers.

Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel

Proceedings of the STACS 2008, 2008

Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract).

Martin Dietzfelbinger, Rasmus Pagh

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Balanced allocation and dictionaries with tightly packed constant size bins.

Martin Dietzfelbinger, Christoph Weidling

Theor. Comput. Sci., 2007

A characterization of average case communication complexity.

Martin Dietzfelbinger, Henning Wunderlich

Inf. Process. Lett., 2007

Design Strategies for Minimal Perfect Hash Functions.

Martin Dietzfelbinger

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2007

07391 Abstracts Collection - Probabilistic Methods in the Design and Analysis of Algorithms.

Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, Berthold Vöcking

Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

2005

On the probability of rendezvous in graphs.

Martin Dietzfelbinger, Hisao Tamaki

Random Struct. Algorithms, 2005

2004

Gossiping and broadcasting versus computing functions in networks.

Martin Dietzfelbinger

Discret. Appl. Math., 2004

Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P"

Martin Dietzfelbinger

Lecture Notes in Computer Science 3000, Springer, ISBN: 3-540-40344-2, 2004

2003

The analysis of a recombinative hill-climber on H-IFF.

Martin Dietzfelbinger, Bart Naudts, Clarissa Van Hoyweghen, Ingo Wegener

IEEE Trans. Evol. Comput., 2003

A case against using Stirling's formula (unless you really need it).

Martin Dietzfelbinger, Manfred Kunde

Bull. EATCS, 2003

Almost random graphs with simple hash functions.

Martin Dietzfelbinger, Philipp Woelfel

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

The Probability of a Rendezvous is Minimal in Complete Graphs.

Martin Dietzfelbinger

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

2001

On Different Models for Packet Flow in Multistage Interconnection Networks.

Martin Dietzfelbinger, Anna Gambin, Slawomir Lasota

Fundam. Informaticae, 2001

Simple Minimal Perfect Hashing in Less Space.

Martin Dietzfelbinger, Torben Hagerup

Proceedings of the Algorithms, 2001

1999

Linear Hash Functions.

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos

J. ACM, 1999

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape.

Martin Dietzfelbinger, Martin Hühne

Comput. Complex., 1999

1997

A Reliable Randomized Algorithm for the Closest-Pair Problem.

Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, Martti Penttonen

J. Algorithms, 1997

Is Linear Hashing Good?

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

A Comparison of Two Lower-Bound Methods for Communication Complexity.

Martin Dietzfelbinger, Juraj Hromkovic, Georg Schnitger

Theor. Comput. Sci., 1996

Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines.

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

SIAM J. Comput., 1996

The Linear-Array Problem in Communication Complexity Resolved

Martin Dietzfelbinger

Electron. Colloquium Comput. Complex., 1996

Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes.

Martin Dietzfelbinger

Proceedings of the STACS 96, 1996

1995

Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

Electron. Colloquium Comput. Complex., 1995

1994

Dynamic Perfect Hashing: Upper and Lower Bounds.

Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert Endre Tarjan

SIAM J. Comput., 1994

Exact Lower Time Bounds for Computing Boolean Functions on CREW PRAMs.

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

J. Comput. Syst. Sci., 1994

Matching Upper and Lower Bounds for Simulation of Several Tapes on One Multidimensional Tape.

Martin Dietzfelbinger, Martin Hühne

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

1993

An Optimal Parallel Dictionary

Martin Dietzfelbinger, Friedhelm Meyer auf der Heide

Inf. Comput., February, 1993

The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines with Output Tape.

Martin Dietzfelbinger, Wolfgang Maass

Theor. Comput. Sci., 1993

Simple, Efficient Shared Memory Simulations.

Martin Dietzfelbinger, Friedhelm Meyer auf der Heide

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Simulations Between Different Models of Parallel Computers.

Martin Dietzfelbinger

Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

1992

A Perfect Parallel Dictionary.

Hannah Bast, Martin Dietzfelbinger, Torben Hagerup

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Polynomial Hash Functions Are Reliable (Extended Abstract).

Martin Dietzfelbinger, Joseph Gil, Yossi Matias, Nicholas Pippenger

Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

High Performance Universal Hashing, with Applications to Shared Memory Simulations.

Martin Dietzfelbinger, Friedhelm Meyer auf der Heide

Proceedings of the Data Structures and Efficient Algorithms, 1992

Dynamic Hashing in Real Time.

Martin Dietzfelbinger, Friedhelm Meyer auf der Heide

Proceedings of the Informatik, Festschrift zum 60. Geburtstag von Günter Hotz, 1992

1991

The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines.

Martin Dietzfelbinger, Wolfgang Maass, Georg Schnitger

Theor. Comput. Sci., 1991

Three disjoint path paradigms in star networks.

Martin Dietzfelbinger, Seshu Madhavapeddy, Ivan Hal Sudborough

Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, 1991

1990

How to Distribute a Dictionary in a Complete Network

Martin Dietzfelbinger, Friedhelm Meyer auf der Heide

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Exact Time Bounds for Computing Boolean Functions on PRAMs Without Simultaneous Writes.

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

A New Universal Class of Hash Functions and Dynamic Hashing in Real Time.

Martin Dietzfelbinger, Friedhelm Meyer auf der Heide

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989

Lower Bounds for Sorting of Sums.

Martin Dietzfelbinger

Theor. Comput. Sci., 1989

The Speed of Copying on One-Tape Off-Line Turing Machines.

Martin Dietzfelbinger

Inf. Process. Lett., 1989

1988

Lower Bound Arguments with "Inaccessible" Numbers.

Martin Dietzfelbinger, Wolfgang Maass

J. Comput. Syst. Sci., 1988

Upper and Lower Bounds for the Dictionary Problem (Abstract).

Martin Dietzfelbinger, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert

Proceedings of the SWAT 88, 1988

1987

Lower bounds on computation time for various models in computational complexity theory.

Martin Dietzfelbinger

PhD thesis, 1987

1986

two Lower Bound Arguments with "Inaccessible" Numbers.

Martin Dietzfelbinger, Wolfgang Maass

Proceedings of the Structure in Complexity Theory, 1986