Detailansicht
Privatizing and dynamizing algorithm design
Sricharan Arunapuram Rangaramanujam
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doktoratsstudium der technischen Wissenschaften Informatik
Betreuer*innen
Gramoz Goranci ,
Monika Henzinger
DOI
10.25365/thesis.80402
URN
urn:nbn:at:at-ubw:1-15694.36610.644375-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das Entwerfen von Algorithmen entwickelte sich von Ansätzen mit nur minimalen Annahmen über die Einsatzumgebung hin zu solchen, die an eine Vielzahl unterschiedlicher Rahmenbedingungen angepasst sind. Zwei solcher Rahmenbedingungen sind aufgrund praktischer Anforderungen besonders in den Vordergrund gerückt: Zum Einen verlangen Datenschutzgesetze die Privatisierung personenbezogener Daten, was zu einem Interesse an Algorithmen geführt hat, die zusätzlich nachweisbare Datenschutzgarantien erfüllen. Andererseits erfordert die große Menge an Daten, die kontinuierlich erzeugt und gesammelt wird, Algorithmen, die effizient auf solchen dynamischen Daten arbeiten können. In dieser Arbeit untersuchen wir Algorithmen für diese beiden Einsatzgebiete. Ein verbindendes Thema der hier vorgestellten Algorithmen ist die Datenkomprimierung oder -verdichtung, um die betrachteten Probleme zu vereinfachen. Wir zeigen, wie man - einen annähernd maximalen Fluss, wenn Kanten zum Graphen hinzugefügt werden, - einen oblivious Routing-Algorithmus mit geringer Überlastung, der in weniger Iterationen benötigt als baumbasierte Router, - bedingte Härte für klassische Graphenprobleme auf strukturierten Graphenklassen wie Expandern, - private Präfixsummen eines Vektorstroms mit weniger Fehlern als der Stand der Technik, wenn der Strom spärlich ist, - private Schätzungen der Anzahl unterschiedlicher Elemente in einer sich entwickelnden Population, und - einen dichten Teilgraphen privat mithilfe eines privaten Streaming-Präfixsummen-Algorithmus ermittelt, erhält.
Abstract
(Englisch)
Algorithm design has progressed from approaches with only minimal assumptions about the environment that the algorithm operates in, to those that are adapted to work under a variety of settings. Two such settings have come to the forefront due to practical concerns: Data privacy laws require personal data to be privatized, leading to an interest in algorithms that additionally satisfy provable privacy guarantees; at the same time, the large amount of data that is continuously generated and collected necessitates algorithms that can run efficiently on such evolving data. We study algorithms for these two settings in this thesis. A unifying theme of the algorithms presented here is that of data compression or sparsification to simplify the problems considered. We show how to obtain - an approximately maximum flow as edges get added to the graph, - a low congestion oblivious routing algorithm that runs in lesser iterations than tree-based routers, - conditional hardness for classical graph problems on structured graph classes such as expanders, - private prefix sums of a stream of vectors with lesser error than state-of-the-art when the stream is sparse, - private estimates of the number of distinct elements in an evolving population, and - a dense subgraph privately using a private streaming prefix sum algorithm.
Schlagwörter
Schlagwörter
(Deutsch)
dynamischer algorithmus differential privacy
Schlagwörter
(Englisch)
theoretical computer science differential privacy dynamic algorithms algorithm design
Autor*innen
Sricharan Arunapuram Rangaramanujam
Haupttitel (Englisch)
Privatizing and dynamizing algorithm design
Publikationsjahr
2025
Umfangsangabe
190 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Tsz Hong Hubert Chan ,
Sayan Bhattacharya
Klassifikation
54 Informatik > 54.10 Theoretische Informatik
AC Nummer
AC17784344
Utheses ID
78800
Studienkennzahl
UA | 786 | 880 | |