3 papers
cs.LG2020
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…
cs.CC2019
Universal Communication, Universal Graphs, and Graph Labeling
Nathaniel Harms
We introduce a communication model called universal SMP, in which Alice and Bob receive a function belonging to a family , and inputs and . Alice and Bob us…
cs.DS2018
Testing Halfspaces over Rotation-Invariant Distributions
Nathaniel Harms
We present an algorithm for testing halfspaces over arbitrary, unknown rotation-invariant distributions. Using random examples of an unknown function …