PhD defence by Jakub Tětek
Follow this link to participate on Zoom
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.