Königstein Fortress

Hi!

This is the personal website of Hendrik Fichtenberger. It's the place where I collect various bits and pieces that I wrote, developed or like. If you'd like to get in touch, feel free to drop me an  email!

Research

I'm a computer scientist, and my interests lie in designing and analyzing algorithms for large data. My research originates in theoretical computer science, and I've worked on sublinear, dynamic, clustering and graph algorithms. However, I also enjoy to implement neat algorithms, and some of our papers have actually been implemented by my coauthors and me. I obtained my Ph.D. at  TU Dortmund in the research group of my doctoral advisor Christian Sohler. Afterwards, I was as a postdoc in Monika Henzinger's group at the  University of Vienna. Currently, I work in the  Graph Mining team at  Google Research in Zürich.

My ORCID iD is  0000-0003-3246-5323. And of course, no computer scientist can hide from  dblp and  Google Scholar.

  • Property Testing of Graphs and the Role of Neighborhood Distributions,
     Ph.D. thesis.  official version  slides
  • Explicit Upper Bounds on the Minimum Size of Planar Graphs That Satisfy a Given Distribution of k-Disks,
    Master's thesis.  self-archived version

Publications

  • J. Blocki, H. Fichtenberger, E. Grigorescu and T. Mukherjee
    “Differential Privacy and Sublinear Time are Incompatible Sometimes,”
    to appear in 16th Innovations in Theoretical Computer Science (ITCS),
    2025.  arXiv version
  • W. He, H. Fichtenberger and P. Peng
    “A Differentially Private Clustering Algorithm for Well-Clustered Graphs,”
    in 12th International Conference on Learning Representations (ICLR),
    2024.  conference version  arXiv version
  • H. Fichtenberger, M. Henzinger and J. Upadhyay
    “Constant Matters: Fine-grained Complexity of Differentially Private Continual Observation.”
    in 40th International Conference on Machine Learning (ICML),
    2023.  conference version  arXiv version
  • B. A. Mayer, A. Tsitsulin, H. Fichtenberger, J. Halcrow and B. Perozzi
    “HUGE: Huge Unsupervised Graph Embeddings with TPUs”
    in 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD),
    2023.  conference version
  • M. Bateni, H. Esfandiari, H. Fichtenberger, M. Henzinger, R. Jayaram, V. Mirrokni and A. Wiese
    “Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries”
    in 34th Symposium on Discrete Algorithms (SODA),
    2023.  conference version  arXiv version
  • H. Fichtenberger and P. Peng
    “Approximately Counting Subgraphs in Data Streams,”
    in 41st Symposium on Principles of Database Systems (PODS),
    2022.  conference version  arXiv version
  • H. Fichtenberger, M. Henzinger and L. Ost
    “Differentially Private Algorithms for Graphs Under Continual Observation,”
    in 29th Annual European Symposium on Algorithms (ESA),
    2021.  conference version  arXiv version
  • H. Fichtenberger and A. Rey,
    “Testing Stability Properties in Graphical Hedonic Games,”
    in Autonomous Agents and Multi-Agent Systems (JAAMAS),
    2021.  journal version
  • H. Fichtenberger, S. Lattanzi, A. Norouzi-Fard and O. Svensson
    “Consistent k-Clustering for General Metrics,”
    in 32nd Symposium on Discrete Algorithms (SODA),
    2021, pp. 2660–2678.  conference version  arXiv version  slides
  • A. Czumaj, H. Fichtenberger, P. Peng and C. Sohler,
    “Testable Properties in General Graphs and Random Order Streaming,”
    in 24th International Conference on Randomization and Computation (RANDOM),
    2020, pp. 16:1–16:20.  conference version  arXiv version  slides
  • H. Fichtenberger, M. Gao and P. Peng,
    “Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time,”
    in 47th International Colloquium on Automata, Languages and Programming (ICALP),
    2020, pp. 45:1–45:13.  conference version  arXiv version  slides
  • H. Fichtenberger, A. Krivošija and A. Rey,
    “Testing Individual-Based Stability Properties in Graphical Hedonic Games,”
    in 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS),
    2019, pp. 882–890.  conference version  arXiv version  journal version
  • H. Fichtenberger, P. Peng and C. Sohler,
    “Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty,”
    in 30th Symposium on Discrete Algorithms (SODA),
    2019, pp. 714–726.  conference version  conference slides  extended slides
  • H. Fichtenberger and D. Rohde,
    “A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice,”
    in 32nd Conference on Neural Information Processing Systems (NeurIPS, formerly NIPS),
    2018, pp. 6743–6754.  conference version  arXiv version  source code
  • H. Fichtenberger and Y. Vasudev,
    “A Two-Sided Error Distributed Property Tester For Conductance,”
    in 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS),
    2018, pp. 19:1–19:15.  conference version  slides
  • H. Fichtenberger, R. Levi, Y. Vasudev and M. Wötzel,
    “A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error,”
    in 45th International Colloquium on Automata, Languages, and Programming (ICALP),
    2018, pp. 52:1–52:14.  conference version  arXiv version  slides  poster
  • H. Fichtenberger, P. Peng and C. Sohler,
    “On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs,”
    in 19th International Workshop on Randomization and Computation (RANDOM),
    2015, pp. 786–799.  conference version  slides
  • D. Siedhoff, H. Fichtenberger, P. Libuschewski, F. Weichert, C. Sohler and H. Müller,
    “Signal/Background Classification of Time Series for Biological Virus Detection,”
    in 36th Annual German Pattern Recognition Symposium (GCPR),
    2014, pp. 388–398.  conference version  self-archived version
  • H. Fichtenberger, M. Gillé, M. Schmidt, C. Schwiegelshohn and C. Sohler,
    “BICO: BIRCH Meets Coresets for k-Means Clustering,”
    in 21st Annual European Symposium on Algorithms (ESA),
    2013, pp. 481–492.  conference version  self-archived version  slides  source code
  • show all…

Projects

Some of my personal or work-related projects are available on  GitHub or their respective project websites.
  • Klausuransicht

     repository  live demo

    Klausuransicht, exam view, is a web app (texts in German only) that can be used to project information such as a clock, remaining time and rules during exams, e.g., at university. Once loaded, it runs locally in the browser.

  • BICO: k-means coresets and clusterings in streams

     Homepage of the project

    Clustering is a method to group objects that are similar with respect to some property (e.g., color). BICO is a streaming algorithm to compute k-means clusterings, more precisely, to compute k-means coresets. This implementation is the experimental part's core of our paper on this topic. It is suited for production use and provides better solutions in less time than many other algorithms. You can download the C++ sources  here. There also exists a  Java implementation for MOA and an adaption of the C++ implementation for the  R package stream.

  • CluE: a clustering library

     Homepage of the project

    There exist many clustering algorithms for various objectives. CluE is a C++ library that implements several clustering algorithms. It was funded by  DFG.

  • PROBI: probabilistic k-median in streams

     Homepage of the project

    From the perspective of edit distance, k-means and k-median objectives look almost the same. However, algorithmically, the two problems are tackled quite differently. PROBI is an algorithm for k-median for regular and probabilistic inputs. This is a proof of concept implementation. You can download the C++ sources  here.

  • FIBS: job scheduler using files to communicate

     Homepage of the project

    Sometimes when you perform the same experiment ten or a hundred times, you realize that a single machine won't do anymore. However, you're still at an early stage and you don't want to migrate to a computing cluster right now (maybe you should, but…). There might be a bunch of computers around that don't need any reservation or scripting of workload managers, but there's nothing that connects them but a shared folder somewhere in the local network or in the cloud.

    FIBS is a Python script that reads a simple job file, distributes jobs to available workers, takes care of running the jobs and collects the results – all by just using the shared folder. It's probably not what you want to use at a large scale, but it's simple and easy to set up.

  • Inkscape Export Overlays: export slides with overlays

     Homepage of the project

     Inkscape is a very cool, free and open-source vector graphics editor. I use it to draw posters and slides. When creating slides with overlays (step-by-step animations), there are typically a lot of layers that need to be activated or deactivated in order to export specific overlays. This extension, which is forked from  the inkscape-export-layers extension by Jesús Espino and Xavier Julian, adds the ability to mark layers as active for a range of overlays and export all overlays automatically at once to, e.g., PDF or PDF+LaTeX.