9 papers
Distributed Gaussian Mean Testing under Communication Constraints: messages, samples, and coins
Clément L. Canonne, Nimitt
We revisit the problem of Gaussian mean testing in a distributed, communication constrained setting, where each of users independently observes samples from an unknown -dime…
Entropy Equivalence Testing
Clément L. Canonne, Yash Pote, Jonathan Scarlett +1
We introduce the problem of \emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution tes…
Uniformity Testing under User-Level Local Privacy
Clément L. Canonne, Abigail Gentle, Vikrant Singhal
We initiate the study of distribution testing under \emph{user-level} local differential privacy, where each of users contributes samples from the unknown underlying distri…
NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria
Eason Yu, Tzu Hao Liu, Clément L. Canonne +4
Finding Nash equilibria in two-player zero-sum imperfect-information games remains a central challenge in multi-agent reinforcement learning. Recent multi-round regularization meth…
Instance-Optimal Uniformity Testing and Tracking
Guy Blanc, Clément L. Canonne, Erik Waingarten
In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the unifo…
Zero-Shot Attribution for Large Language Models: A Distribution Testing Approach
Clément L. Canonne, Yash Pote, Uddalok Sarkar
A growing fraction of all code is sampled from Large Language Models (LLMs). We investigate the problem of attributing code generated by language models using hypothesis testing to…
Gaussian Mean Testing under Truncation
Clément L. Canonne, Themis Gouleakis, Yuhao Wang +1
We consider the task of Gaussian mean testing, that is, of testing whether a high-dimensional vector perturbed by white noise has large magnitude, or is the zero vector. This quest…
Uniformity testing when you have the source code
Clément L. Canonne, Robin Kothari, Ryan O'Donnell
We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the di…
Locally Private Histograms in All Privacy Regimes
Clément L. Canonne, Abigail Gentle
Frequency estimation, a.k.a. histograms, is a workhorse of data analysis, and as such has been thoroughly studied under differentially privacy. In particular, computing histograms…