Martin Dietzfelbinger

According to our database1, Martin Dietzfelbinger authored at least 88 papers between 1986 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths.
Combinatorics, Probability & Computing, 2019

Constant-Time Retrieval with O(log m) Extra Bits.
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.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Dense Peelable Random Uniform Hypergraphs.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Determining Minimum Hash Width for Hash Chains.
Proceedings of the Third Central European Cybersecurity Conference, 2019

Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox
Springer, ISBN: 978-3-030-25208-3, 2019

2018
A Subquadratic Algorithm for 3XOR.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Universal Hashing via Integer Arithmetic Without Primes, Revisited.
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.
Inf. Comput., 2017

Theory and Applications of Hashing (Dagstuhl Seminar 17181).
Dagstuhl Reports, 2017

2016
How Good Is Multi-Pivot Quicksort?
ACM Trans. Algorithms, 2016

Optimal Partitioning for Dual-Pivot Quicksort.
ACM Trans. Algorithms, 2016

Preface of STACS 2013 Special Issue.
Theory Comput. Syst., 2016

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

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

2015
Towards Optimal Degree Distributions for Left-Perfect Matchings in Random Bipartite Graphs.
Theory Comput. Syst., 2015

On testing single connectedness in directed graphs and some related problems.
Inf. Process. Lett., 2015

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

Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Algorithmen und Datenstrukturen - die Grundwerkzeuge.
eXamen.press, Springer, ISBN: 978-3-642-05471-6, 2014

2013
Optimal Partitioning for Dual Pivot Quicksort - (Extended Abstract).
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs.
Proceedings of the Experimental Algorithms - 11th International Symposium, 2012

On Randomness in Hash Functions (Invited Talk).
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

2011
Precision, Local Search and Unimodal Functions.
Algorithmica, 2011

Cuckoo Hashing with Pages.
Proceedings of the Algorithms - ESA 2011, 2011

Fingerprinting.
Proceedings of the Algorithms Unplugged, 2011

2010
Ingo Wegener: seine Bücher.
Informatik Spektrum, 2010

Tight Bounds for Blind Search on the Integers and the Reals.
Combinatorics, Probability & Computing, 2010

Tight Thresholds for Cuckoo Hashing via XORSAT.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009
In memoriam Prof. Dr. math. Ingo Wegener, 1950-2008.
Theor. Comput. Sci., 2009

Tight lower bounds for greedy routing in uniform small world rings.
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.
Proceedings of the SOFSEM 2009: Theory and Practice of Computer Science, 2009

On risks of using cuckoo hashing with simple universal hash classes.
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.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

Perfect Hashing for State Spaces in BDD Representation.
Proceedings of the KI 2009: Advances in Artificial Intelligence, 2009

Applications of a Splitting Trick.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Hash, Displace, and Compress.
Proceedings of the Algorithms, 2009

Experimental Variations of a Theoretically Good Retrieval Data Structure.
Proceedings of the Algorithms, 2009

2008
Fingerprinting.
Proceedings of the Taschenbuch der Algorithmen, 2008

A dictionary implementation based on dynamic perfect hashing.
ACM Journal of Experimental 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.
Computer Science Review, 2008

Succinct Data Structures for Retrieval and Approximate Membership
CoRR, 2008

Tight Bounds for Blind Search on the Integers.
Proceedings of the STACS 2008, 2008

Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007
Balanced allocation and dictionaries with tightly packed constant size bins.
Theor. Comput. Sci., 2007

A characterization of average case communication complexity.
Inf. Process. Lett., 2007

Design Strategies for Minimal Perfect Hash Functions.
Proceedings of the Stochastic Algorithms: Foundations and Applications, 2007

07391 Abstracts Collection - Probabilistic Methods in the Design and Analysis of Algorithms.
Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

2005
On the probability of rendezvous in graphs.
Random Struct. Algorithms, 2005

2004
Primality Testing in Polynomial Time, From Randomized Algorithms to "PRIMES Is in P"
Lecture Notes in Computer Science 3000, Springer, ISBN: 3-540-40344-2, 2004

2003
The analysis of a recombinative hill-climber on H-IFF.
IEEE Trans. Evolutionary Computation, 2003

A case against using Stirling's formula (unless you really need it).
Bulletin of the EATCS, 2003

Almost random graphs with simple hash functions.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
The Probability of a Rendezvous is Minimal in Complete Graphs.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

2001
On Different Models for Packet Flow in Multistage Interconnection Networks.
Fundam. Inform., 2001

Simple Minimal Perfect Hashing in Less Space.
Proceedings of the Algorithms, 2001

1999
Linear Hash Functions.
J. ACM, 1999

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

1997
A Reliable Randomized Algorithm for the Closest-Pair Problem.
J. Algorithms, 1997

Is Linear Hashing Good?
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.
Theor. Comput. Sci., 1996

Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines.
SIAM J. Comput., 1996

The Linear-Array Problem in Communication Complexity Resolved
Electronic Colloquium on Computational Complexity (ECCC), 1996

Gossiping and Broadcasting versus Computing Functions in Networks
Electronic Colloquium on Computational Complexity (ECCC), 1996

Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes.
Proceedings of the STACS 96, 1996

1995
Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs
Electronic Colloquium on Computational Complexity (ECCC), 1995

1994
Dynamic Perfect Hashing: Upper and Lower Bounds.
SIAM J. Comput., 1994

Exact Lower Time Bounds for Computing Boolean Functions on CREW PRAMs.
J. Comput. Syst. Sci., 1994

Matching Upper and Lower Bounds for Simulation of Several Tapes on One Multidimensional Tape.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

1993
An Optimal Parallel Dictionary
Inf. Comput., February, 1993

The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines with Output Tape.
Theor. Comput. Sci., 1993

Simple, Efficient Shared Memory Simulations.
Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

Simulations Between Different Models of Parallel Computers.
Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

1992
A Perfect Parallel Dictionary.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Polynomial Hash Functions Are Reliable (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

High Performance Universal Hashing, with Applications to Shared Memory Simulations.
Proceedings of the Data Structures and Efficient Algorithms, 1992

Dynamic Hashing in Real Time.
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.
Theor. Comput. Sci., 1991

Three disjoint path paradigms in star networks.
Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, 1991

1990
How to Distribute a Dictionary in a Complete Network
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Exact Time Bounds for Computing Boolean Functions on PRAMs Without Simultaneous Writes.
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.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989
Lower Bounds for Sorting of Sums.
Theor. Comput. Sci., 1989

The Speed of Copying on One-Tape Off-Line Turing Machines.
Inf. Process. Lett., 1989

1988
Lower Bound Arguments with "Inaccessible" Numbers.
J. Comput. Syst. Sci., 1988

Upper and Lower Bounds for the Dictionary Problem (Abstract).
Proceedings of the SWAT 88, 1988

1987
Lower bounds on computation time for various models in computational complexity theory.
PhD thesis, 1987

1986
two Lower Bound Arguments with "Inaccessible" Numbers.
Proceedings of the Structure in Complexity Theory, 1986


  Loading...