We study \emph{ripple mechanisms} for pure differentially private computation of discrete statistics. For each of three natural statistics – sum, count, and vote – we construct an efficient instance of the ripple mechanism and show that it is often more accurate than the previous state of the art. We also prove that ripple mechanisms are, in some settings, optimal among all discrete pure differentially private additive noise mechanisms.

We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d^2)$. Experiments show that, depending on the partial order in question, our solution dominates existing pure differentially private mechanisms and can reduce their error by an order of magnitude or more.

Differentially private computation often begins with a bound on some $d$-dimensional statistic’s $\ell_p$ sensitivity. For pure differential privacy, the $K$-norm mechanism can improve on this approach using a norm tailored to the statistic’s sensitivity space. Writing down a closed-form description of this optimal norm is often straightforward. However, running the $K$-norm mechanism reduces to uniformly sampling the norm’s unit ball; this ball is a $d$-dimensional convex body, so general sampling algorithms can be slow. Turning to concentrated differential privacy, elliptic Gaussian noise offers similar improvement over spherical Gaussian noise. Once the shape of this ellipse is determined, sampling is easy; however, identifying the best such shape may be hard. This paper solves both problems for the simple statistics of sum, count, and vote. For each statistic, we provide a sampler for the optimal $K$-norm mechanism that runs in time $\tilde O(d^2)$ and derive a closed-form expression for the optimal shape of elliptic Gaussian noise. The resulting algorithms all yield meaningful accuracy improvements while remaining fast and simple enough to be practical. More broadly, we suggest that problem-specific sensitivity space analysis may be an overlooked tool for private additive noise.

Online whiteboards are becoming a popular way to facilitate collaborative design work, providing a free-form environment to curate ideas. However, as templates are increasingly being used to scaffold contributions from non-experts designers, it is crucial to understand their impact on the creative process. In this paper, we present the results from a study with 114 students in a large introductory design course. Our results confirm prior findings that templates benefit students by providing a starting point, a shared process, and the ability to access their own work from previous steps. While prior research has criticized templates for being too rigid, we discovered that using templates within a free-form environment resulted in visual patterns of free-form curation where concepts were spatially organized, clustered, color-coded, and connected using arrows and lines. We introduce the concept of ‘Free-form Templates’ to illustrate how templates and free-form curation can be synergistic.

First-day mortality prediction is a critical task in the Intensive Care Unit (ICU), as it can help clinicians identify which patients are at the highest risk for death and thus may need more intensive care. Many heuristic-based metrics for first-day mortality exist. However many signals exist in the Electronic Health Record (EHR) that are not used in these metrics. For the implementation of these metrics, it is important to keep the number of required signals as small as possible so that the user can quickly receive an assessment of their patient. In this paper, we leverage techniques from classical machine learning to compare sets of signals from a patients record (like demographic information, lab values, and vital sign measurements) to find the minimum feature set that best informs first day mortality. We compare several feature selection techniques to identify various feature sets with differing number of features. We found that Elastic Net was the overall best performing method and was able to reach the same performance as the current state of the art with less than half the features. This suggests that an optimal feature set is clinically meaningful.

IETF QUIC, the standardized version of Google’s UDP-based layer-4 network protocol, has seen increasing adoption from large Internet companies for its benefits over TCP. Yet despite its rapid adoption, performance analysis of QUIC in production is scarce. Most existing analyses have only used unoptimized open-source QUIC servers on non-tuned kernels: these analyses are unrepresentative of production deployments which raises the question of whether QUIC actually outperforms TCP in practice.