New Results on Hashing, Labeling Schemes and Algorithms

Research output: Book/ReportPh.D. thesis

  • Mathias Bæk Tejs Knudsen

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].

Original languageEnglish
PublisherDepartment of Computer Science, Faculty of Science, University of Copenhagen
Number of pages349
Publication statusPublished - 2017

ID: 183188264