PhD defence by Jakub Tětek

Title

Randomized Algorithms for Large Datasets - Graphs, Streams, and Sums: The Sublinear Trilogy

Abstract

This thesis addresses several challenges in efficiently processing large datasets and in privacy-preserving computation. Specifically, in this thesis, we look into the following problems.
First, we focus on the problem of estimating the sum of numbers under the assumption that we may sample the numbers proportionally to their values.
Second, we focus on several related problems in sublinear-time computation on graphs. We investigate several different models which formalize the setting where we have a very large graph and we want to perform some computation on it without even reading all of it. We consider several problems, namely sampling edges uniformly, counting edges, and counting triangles.
Finally, we consider the well-known Misra-Gries sketch for the problem of approximately finding frequent elements in a stream. We make this sketch differentially private while losing only a minimal amount of accuracy.

Supervisors

Principal Supervisor Mikkel Thorup

Assessment Committee

Associate Professor Srikanth Srinivasan, Department of Computer Science
Professor Petra Berenbrink, Universität Hamburg
Professor Robert Krauthgamer, Weizmann Institute of Science

Moderator: Associate Professor Srikanth Srinivasan, Department of Computer Science

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