PhD Defense by Mathias Bæk Tejs Knudsen: New Results on Hashing, Labeling Schemes and Algorithms


New Results on Hashing, Labeling Schemes and Algorithms


In this thesis, we show several new results on hashing, labeling schemes and algorithms. There is not space in the abstract to mention all the results, but a result from each area is highlighted:

Linear hashing: We consider the classic hash function h(x) = ((ax+b) mod p) mod n, where a,b are chosen uniformly at random from {0,1,2,...,p-1}. We prove that when using h in hashing with chaining the expected size of the longest chain is, which is the first improvement on the folklore bound of . Appeared in [FOCS'16].

Adjacency labeling for trees: We show that there exists an induced universal graph with O(n) nodes for the family of forests on n nodes. We hereby solve an open problem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich [STOC'88], Chung [J. of Graph Theory'90], Fraigniaud and Korman [SODA'10]. Joint work with Alstrup and Dahlgaard [FOCS'15].

Even cycle detection: For any constant k we give an algorithm that in time  determines if a graph with m edges contains a cycle of length 2k. This improves upon a result by Yuster and Zwick [J. Discrete Math 1997] who gave an  algorithm for this problem and noted that it is "plausible to conjecture that  is the best possible bound in terms of n", where n is the number of nodes in the graph. If this conjecture is true, then our result is optimal in terms of n and m. Joint work with Dahlgaard and Stöckel [STOC'17].

Assessment Committee

  • Chairman: Professor Mads Nielsen, Department of Computer Science, University of Copenhagen
  • Professor Robert E. Tarjan, Department of Computer Science, Princeton University
  • Professor Giuseppe F. Italiano, University of Roma “Tor Vergata”

Academic supervisor & Co-supervisor

  • Professor Stephen Alstrup, Department of Computer Science, University of Copenhagen
  • Co-supervisor Professor Mikkel Thorup

For an electronic copy of the thesis, please contact Mathias Bæk Tejs Knudsen