PhD defence by Peter Rasmussen

Title

Graphs, Algorithms, and Discrete Probabilities

Abstract

In this thesis, we prove new results within algorithms, graph theory, and cryptography. Space is too scarce in this abstract to mention them all, so instead we describe a couple.

Hashing Algorithms: To handle the overwhelming amounts of data stored in today's world, it is necessary to employ fast algorithms. The data sets are often either too large to allow exact computation or arrives in streams too vast to store. In such cases, exact computation is out of the question, and we must instead rely on randomized approximations instead. A powerful tool in that regard is the use of hash functions. In algorithmic analysis, hash functions are often assumed to be fully random functions. However, in practice, hash functions are merely succinct approximations of random functions and cannot satisfy the guarantees of fully random functions. A common way to handle this disparity is to run an algorithm multiple times in parallel and combine the resulting estimates to obtain stronger guarantees. In our work, we introduce a new fast and easily implementable hash function, tabulation-permutation hashing. We prove that in settings where hash functions are commonly applied, they provide guarantees almost as good as a fully random function. Furthermore, we prove and demonstrate experimentally that algorithms for counting the number of distinct elements in a data stream and for estimating similarity between large data sets achieve higher precision and faster execution when implemented with our new hash function.

Decremental Dynamic Connectivity: Consider a network consisting of network nodes and connections between pairs of nodes. A very basic question to ask is the following: Standing at one node, can we through the connections between nodes reach another node? If so, we say that the nodes are connected in the network. A common trait of networks is that they change over time. To be able to answer questions regarding such networks, dynamic algorithms are employed. Dynamic algorithms come in three flavors: fully dynamic, incremental dynamic, and decremental dynamic algorithms, where connections are either both added and removed, only added, and only removed, respectively. The question of connectivity is one of the most well studied dynamic problems on networks and there are near-optimal algorithms for the fully dynamic and the incremental dynamic case. In this thesis, we present an optimal algorithm for the decremental dynamic connectivity problem for all graphs that are not sparse. Previously, optimal algorithms for this problem were only known for very dense graphs.

Assessment Committee

Chair: Professor, Rasmus Pagh, Department of Computer Science, UCPH

Professor, Valerie King, University of Victoria, Canada

Professor, Uri Zwick, University of Tel-Aviv, Israel

Academic Supervisor

Professor, Mikkel Thorup, Department of Computer Science, UCPH

Moderator for this defence will be

Assistant professor, Mikkel Abrahamsen, Department of Computer Science,
University of Copenhagen

This defence will be conducted both physically and online.

For an electronic copy of the thesis, please go to the PhD Programme page.