Hendrik Fichtenberger
Research Areas
Authored Publications
Sort By
Preview abstract
Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Yet, research has so far concentrated on one or the other. The existence of private algorithms and, separately, sublinear algorithms for many problems poses the question of differential privacy and sublinear time can be combined. Little is known so far, especially when it comes to hardness results on these algorithms. In this paper, we initiate the study of lower bounds for differentially private, sublinear time algorithms. Our main result is the incompatibility of both in the general case. In particular, we prove that a simple problem based on one-way marginals yiels both, a differentially private algorithm and a sublinear time algorithm, but a substantially sublinear time, differentially private algorithm does not exist.
View details
Constant Matters: Fine-grained Complexity of Differentially Private Continual Observation
Preview
Monika Henzinger
Jalaj Upadhyay
Proceedings of the 40th International Conference on Machine Learning (ICML) (2023)
Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
Preview
Monika Henzinger
Andreas Wiese
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
HUGE: Huge Unsupervised Graph Embeddings with TPUs
SIGKDD Conference on Knowledge Discovery and Data Mining, ACM (2023) (to appear)
Preview abstract
Graphs are a representation of structured data that captures the relationships between sets of objects. With the ubiquity of available network data, there is increasing industrial and academic need to quickly analyze graphs with billions of nodes and trillions of edges. A common first step for network understanding is Graph Embedding, the process of creating a continuous representation of nodes in a graph. A continuous representation is often more amenable, especially at scale, for solving downstream machine learning tasks such as classification, link prediction, and clustering. A high-performance graph embedding architecture leveraging Tensor Processing Units (TPUs) with configurable amounts of high-bandwidth memory is presented that simplifies the graph embedding problem and can scale to graphs with billions of nodes and trillions of edges. We verify the embedding space quality on real and synthetic large-scale datasets.
View details
