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://rex.kb.dk/primo-explore/fulldisplay?docid=KGL01010646748&context=L&vid=NUI&search_scope=KGL&tab=default_tab&lang=da_DK
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 -