2 papers
cs.DS2026
Distribution-Free Halfspace Testing with Samples
Xi Chen, Renato Ferreira Pinto, Nathaniel Harms +2
We prove a tight lower bound on the number of samples required for testing halfspaces over , in the distribution-free sample-based model where the underlying…
cs.DS2026
Testing Support Size More Efficiently Than Learning Histograms
Renato Ferreira Pinto, Nathaniel Harms
Consider two problems about an unknown probability distribution : 1. How many samples from are required to test if is supported on elements or not? Specifically, giv…