8 problems

For distributions $\mathbf{p},\mathbf{q}$ on $\mathbb{R}^d$ and an axis-aligned rectangle $R\subset\mathbb{R}^d$ satisfying … let $x,y$ be sampled from the distribution…

Let $[d]=\{1,\ldots,d\}$, and consider private uniformity testing of discrete distributions over $[d]$ and private uniformity testing of product distributions over $\{-1,1\}^d$. Ca…

Let the closeness tester be the chi-squared-based tester for distinguishing whether two unknown discrete distributions are equal or are at least a specified distance apart. Optimal…

Optimal private testing sample complexity conjecture. This sample complexity is optimal, up to logarithmic factors; equivalently, the required number of samples is…

For a finite-state Markov chain with state-space size $d$ and testing accuracy parameter $\varepsilon$, let $\mathrm{Dist}_{\sqrt{\phantom{x}}}$ denote the pseudo-distance … where…

Linear dependence conjecture. The sample complexity required for uniformity testing against distributions at distance $\varepsilon$ from $\mathbf{q}$ should have dependence

Sample complexity conjecture. The correct sample complexity for identity testing is

Let $D_1$ and $D_2$ be two unknown probability distributions over $[N]=\{1,\ldots,N\}$. A $\operatorname{COND}$ algorithm is an algorithm that accesses distributions through condit…