This is a heavily interactive web application, and JavaScript is required. Simple HTML interfaces are possible, but that is not what this is.
Post
Clément Canonne
ccanonne.github.io
did:plc:ac6qioenkpl3jmmnib3tpbhb
It took me a while, but I (finally) wrote a "short" (erm) note on the "polynomial+moments method" to prove testing or indistinguishability sample complexity lower bounds. Including the infamous Ω(k/log k) tolerant uniformity testing one.
Comments and feedback welcome!
📝 https://github.com/ccanonne/probabilitydistributiontoolbox/blob/master/testinglowerbounds-polynomial-method.pdf
[contains quote post or other embedded content]
2025-08-17T11:56:38.907Z