TY - BOOK

T1 - New Results on Hashing, Labeling Schemes and Algorithms

AU - Knudsen, Mathias Bæk Tejs

PY - 2017

Y1 - 2017

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

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

UR - https://soeg.kb.dk/permalink/45KBDK_KGL/fbp0ps/alma99122260780805763

M3 - Ph.D. thesis

BT - New Results on Hashing, Labeling Schemes and Algorithms

PB - Department of Computer Science, Faculty of Science, University of Copenhagen

ER -