Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Instance-optimal estimation of L2-norm
event speaker icon
Tomer Adar (Technion)
event date icon
Wednesday, 10.06.2026, 13:00
event location icon
Taub 401

The L2-norm, or collision norm, is a core entity in the analysis of distributions and probabilistic algorithms. Batu and Canonne (FOCS 2017) presented an extensive analysis of algorithmic aspects of the L2-norm and its connection to uniformity testing. However, when it comes to estimating the L2-norm itself, their algorithm is not always optimal compared to the instancespecific second-moment bounds, O(1/(ε∥µ∥2) + tµ/ε2 ), for tµ = ∥µ∥ 3 3/∥µ∥ 4 2 − 1, as stated by Batu (WoLA 2025, open problem session). In this paper, we present an unbiased L2-estimation algorithm whose sample complexity matches the instance-specific second-moment analysis. Additionally, we show that Ω(1/(ε∥µ∥2)+ tµ/ε2 ) is indeed the per-instance lower bound for estimating the norm of a distribution µ by sampling (even for non-unbiased estimators).

https://arxiv.org/pdf/2602.21937