Efficient algorithms

The goal of this project is to design efficient algorithms with desirable properties. Specifically, we will study two algorithmic questions, namely the design of algorithms that protect the privacy of individuals and the design of algorithms that reduce the amount of high-dimensional data by summarizing the data. In both cases we will work on changing data sets. Data sets containing sensitive information about individuals and their relationships are often valuable sources of information. Consider for example data sets about the efficiency of a vaccine for COVID19. However, publishing useful statistics about such data or properties of the underlying structure without leaking individual information is a challenging problem. A class of algorithms that allow to quantify and reduce the amount of data leakage about any individual are called differentially private algorithms. Differential private algorithms have one or multiple design parameters that are used to quantify the amount and the probability of data leakage. Differentially private algorithms for a large set of computational problems such as determining percentage of cell phone users that are interested in health-related information have been developed and deployed in the last ten years. The basic idea is to add suitable random noise to the data at different stages of the algorithm to guarantee (a) that any data leakage is within the values given by the design parameters and (b) that useful information is returned, i.e., that the error introduced by the random noise is minimized. However, almost all of these algorithms assume that all the data is given at the start of the algorithm. In real-world applications input data is rarely static, instead it frequently changes dynamically. The development of differentially private algorithms for dynamically changing data sets is, however, still in its infancy. Thus, the first goal of this project is to develop such algorithms for a large variety of possible applications. We will focus especially on popular input formats such as rows of numerical data, networks, or points in high-dimensional space, which could represent feature vectors of machine learning applications. For such input data we want to develop algorithms that fulfill the privacy design parameters, minimize the introduced error, and are fast. Our second goal is to create summaries of dynamic high-dimensional data by grouping data points that are ``close into sets, called clusters. There exist many different such clustering algorithms, but they usually assume that the complete data set is given at the beginning and it does not change afterwards. In real-world applications this is often not the case as additional data is collected and existing data is corrected. Thus, we plan to design new clustering algorithms that can efficiently be updated when there are changes to the data set.