Our upper bound is based solely on a particular triangular substructure possessed by the graph. We show that, if you just consider this triangular substructure, you can't do better than k^1.5. So one needs to turn to richer structure of the Scheffe Graph to go further

The best part is that the paper is short and sweet: only 10 pages for all the technical content! So please check it out -- and meet me and Matt at #NeurIPS2025 in SD, Wednesday 11 AM poster session, Exhibit Hall C,D,E #1208 10/10
arxiv.org/abs/2509.16180

We were then able to show that the domination number of this graph was O(k^1.5), leading to a non-interactive algorithm with the same sample complexity! Recall this is better than the naive O(k^2) sample algorithm, and "halfway" to the lower bound of Omega(k). 9/n

Until my student Matt Regehr came along! He came up with a brilliant generalization of the minimum distance estimator! With this framework, he reduced the problem to analyzing the domination number of a particular graph structure. 8/n

Unfortunately, interactivity is cumbersome for deployment of local privacy. And the non-interactive O(k^2) algorithm is the naive one. Can we do better?

This is surprisingly hard to answer. I tried for a while, but no luck. 7/n

That said, can we achieve that? In a previous work with
Gopi, Kulkarni, @thesasho.bsky.social, Wu, and Zhang, we gave two algorithms:
1. An interactive ~O(k) sample algorithm
2. A non-interactive O(k^2) sample algorithm 6/n

But what if you consider the stronger constraint of local differential privacy? The bad news: a construction of Duchi and Rogers implies that you need Omega(k) samples. Exponentially more than in the centrally private case! 5/n

The challenge is when you consider privacy constraints. In work with Mark Bun, @stein.ke, and @zstevenwu.bsky.social, we showed that log k samples still suffice under (central) differential privacy. arxiv.org/abs/1905.13229 4/n

As stated, this problem is quite well understood. Work by Yatracos, and later popularized by Devroye and Lugosi, shows that log(k) samples suffice. There's a host of different algorithms that work, including the Scheffe estimator and the minimum distance estimator 3/n

Hypothesis selection is the following problem: given n samples from a probability distribution, and k hypothesis distributions, how do you learn which one is (nearly) the closest? 2/n

ICYMI here's a small fraction of the talent at NYU
bsky.app/profile/gaut...