4 citations · 5 across the 6 of their papers we have counts for
7 papers · 1 filter
Testing and Learning Convex Sets in the Ternary Hypercube
Hadley Black, Eric Blais, Nathaniel Harms
We study the problems of testing and learning high-dimensional discrete convex sets. The simplest high-dimensional discrete domain where convexity is a non-trivial property is the…
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…
Optimal Adjacency Labels for Subgraphs of Cartesian Products
Louis Esperet, Nathaniel Harms, Viktor Zamaraev
For any hereditary graph class , we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in . As a…
Sketching Distances in Monotone Graph Classes
Louis Esperet, Nathaniel Harms, Andrey Kupavskii
We study the two-player communication problem of determining whether two vertices are nearby in a graph , with the goal of determining the graph structures that allow the…
Randomized Communication and Implicit Graph Representations
Nathaniel Harms, Sebastian Wild, Viktor Zamaraev
We initiate the focused study of constant-cost randomized communication, with emphasis on its connection to graph representations. We observe that constant-cost randomized communic…
Downsampling for Testing and Learning in Product Distributions
Nathaniel Harms, Yuichi Yoshida
We study distribution-free property testing and learning problems where the unknown probability distribution is a product distribution over . For many important class…
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 …