A direct comparison of the Valiant-Valiant and Blais-Canonne-Gur functionals for identity testing
The sample complexity of testing identity to a fixed distribution q has been bounded in two ways: by Valiant and Valiant through a truncated ℓ_(2/3) quasinorm Φ_VV(q,ε), and by Blais, Canonne and Gur through the inverse of the ℓ_1–ℓ_2 K-functional, Φ_BCG(q,ε). Canonne asked for a direct proof that the two quantities are related. We prove that Φ_VV(q,ε) ≤ Φ_BCG(q,ε/2) for every probability vector q and every ε ∈ (0,1], and that Φ_BCG(q,ε) ≤ C_c max{1, Φ_VV(q,cε)/ε} for every c ∈ (0,2) and every ε ∈ (0,1/2), with C_c depending only on c. The constant 1, the factor 1/2 and the threshold c<2 cannot be improved, and the factor 1/ε cannot be replaced by ε^(-α) with α<1.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-19
- DOI
- https://doi.org/10.5281/zenodo.24364639
- Primary Topic
- Probability and Statistical Research
- Type
- preprint