Mini-Workshop on Differential Privacy and Algorithms

On October 16, 10:00-13:00, we will host a mini-workshop on differential privacy and algorithms. The talks will take place in Karlsplatz 13, 1040 Wien, in Seminarraum AE U1 - 7.

Talks

Below you can find more detailed information about some of the talks.

Private and Simultaneous Estimation of Symmetric Norms under Continual Observation

Speaker: Bardiya Aryanfard, ISTA

Abstract: In this talk, I will present our recent result on estimating monotone symmetric norms in the continual observation model of differential privacy. In this setting, given a stream of items, upon each update the algorithm outputs an estimate of any monotone symmetric norm on the histogram of the items. Monotone symmetric norms (symmetric norms invariant to sign-flips and permutations) play a vital role in many applications of data analysis, e.g. detecting traffic anomalies and matrix optimization problems. However, ensuring privacy in such settings, particularly under continual observation remains a significant challenge. I will discuss an algorithm that provides differential privacy guarantees while simultaneously estimating all monotone symmetric norms on a frequency vector under continual observation. The talk will cover an introduction to the problem setting, the general ideas behind our algorithm, and an overview on the empirical evaluations.

Incremental Approximate Maximum Flow from Residual Graph Sparsification

Speaker: A. R. Sricharan, Uni Wien

Abstract: We will discuss an incremental algorithm for maintaining a $(1-\epsilon)$-approximate $s$-$t$ max flow in undirected, uncapacitated graphs in total time $\tilde{O}(m + nF^)$, where $m$ is the number of edge insertions and $F^$ is the final max flow value. The result is obtained by extending the residual graph sparsification technique of Karger and Levine [SIAM J. Comput. (2015)] to the incremental setting. Along the way, we will also extend the cut sparsification framework for undirected graphs of Fung et al. [SIAM J. Comput. (2019)] to balanced directed graphs.

Improved Four Cycle Counting in Low Degeneracy Graph Streams

Speaker: Sebastian Lüderssen, TU Wien

Abstract: Given an undirected graph as a data stream of edges in arbitrary order, we consider the problem of estimating the number cycles of length 4 using sublinear space. We present a two-pass streaming algorithm, which returns a (1+epsilon)-approximation of the number of four cycles. A lower bound by McGregor and Vorotnikova (PODS’20) implies that our algorithm has an asymptotically optimal space complexity on bounded-degeneracy graphs.