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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A direct comparison of the Valiant-Valiant and Blais-Canonne-Gur functionals for identity testing

Yitzchak Shmalo
Zenodo (CERN European Organization for Nuclear Research)
Probability and Statistical Research
preprint

A direct comparison of the Valiant-Valiant and Blais-Canonne-Gur functionals for identity testing

Yitzchak Shmalo
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Hebrew University of Jerusalem (IL)
Probability and Statistical Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon