6 papers
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…
Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
Renato Ferreira Pinto
This paper explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $…
Distribution Testing with a Confused Collector
Renato Ferreira Pinto, Nathaniel Harms
We are interested in testing properties of distributions with systematically mislabeled samples. Our goal is to make decisions about unknown probability distributions, using a samp…
Directed Poincaré Inequalities and Monotonicity Testing of Lipschitz Functions
Renato Ferreira Pinto
We study the connection between directed isoperimetric inequalities and monotonicity testing. In recent years, this connection has unlocked breakthroughs for testing monotonicity o…
Distribution Testing Under the Parity Trace
Renato Ferreira Pinto, Nathaniel Harms
Distribution testing is a fundamental statistical task with many applications, but we are interested in a variety of problems where systematic mislabelings of the sample prevent us…
VC Dimension and Distribution-Free Sample-Based Testing
Eric Blais, Renato Ferreira Pinto, Nathaniel Harms
We consider the problem of determining which classes of functions can be tested more efficiently than they can be learned, in the distribution-free sample-based model that correspo…