Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-009 | 27th January 2026 10:58

A short note on (distribution) testing lower bounds via polynomials

RSS-Feed




TR26-009
Authors: Clement Canonne
Publication: 27th January 2026 11:37
Downloads: 58
Keywords: 


Abstract:

In this short expository note, we provide an introduction to a distribution testing (and, more generally, indistinguishability) lower bound method based on moment-matching via polynomials. This method, which underlies several of the tight lower bounds on estimating symmetric properties, had for many years appeared mysterious and near-magical to the author. With this note, he hopes to avoid to others a similar years-long confusion, and enable them to use this very elegant, yet not quite magical, technique.



ISSN 1433-8092 | Imprint