4 citations · 4 across the 8 of their papers we have counts for
13 papers · 1 filter
Differentially Private Substring and Document Counting with Near-Optimal Error
Giulia Bernardini, Philip Bille, Inge Li Gørtz +1
For databases consisting of many text documents, one of the most fundamental data analysis tasks is counting (i) how often a pattern appears as a substring in the database (substri…
Fully Dynamic Graph Algorithms with Edge Differential Privacy
Sofya Raskhodnikova, Teresa Anna Steiner
We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted ove…
Private Counting of Distinct Elements in the Turnstile Model and Extensions
Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner
Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023…
Private graph colouring with limited defectiveness
Aleksander B. G. Christiansen, Eva Rotenberg, Teresa Anna Steiner +1
Differential privacy is the gold standard in the problem of privacy preserving data analysis, which is crucial in a wide range of disciplines. Vertex colouring is one of the most f…
Differentially Private Approximate Pattern Matching
Teresa Anna Steiner
In this paper, we consider the -approximate pattern matching problem under differential privacy, where the goal is to report or count all substrings of a given string which…
Differentially Private Histogram, Predecessor, and Set Cardinality under Continual Observation
Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner
Differential privacy is the de-facto privacy standard in data analysis. The classic model of differential privacy considers the data to be static. The dynamic setting, called diffe…
Compressed Indexing for Consecutive Occurrences
Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya +1
The fundamental question considered in algorithms on strings is that of indexing, that is, preprocessing a given string for specific queries. By now we have a number of efficient s…
Differentially Private Continual Release of Histograms and Related Queries
Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner
We study privately releasing column sums of a -dimensional table with entries from a universe undergoing row updates, called histogram under continual release. Our mecha…
Gapped String Indexing in Subquadratic Space and Sublinear Query Time
Philip Bille, Inge Li Gørtz, Moshe Lewenstein +3
In Gapped String Indexing, the goal is to compactly represent a string of length such that for any query consisting of two strings and , called patterns, and an…
The Fine-Grained Complexity of Episode Matching
Philip Bille, Inge Li Gørtz, Shay Mozes +2
Given two strings and , the Episode Matching problem is to find the shortest substring of that contains as a subsequence. The best known upper bound for this problem…
Gapped Indexing for Consecutive Occurrences
Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen +1
The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient pattern matching queries. Typical queries include existential…
String Indexing for Top- Close Consecutive Occurrences
Philip Bille, Inge Li Gørtz, Max Rishøj Pedersen +2
The classic string indexing problem is to preprocess a string into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a patter…
String Indexing with Compressed Patterns
Philip Bille, Inge Li Gørtz, Teresa Anna Steiner
Given a string of length , the classic string indexing problem is to preprocess into a compact data structure that supports efficient subsequent pattern queries. In this…