4 citations · 5 across the 6 of their papers we have counts for
11 papers
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
Nathaniel Harms, Viktor Zamaraev
We prove a characterization of the structural conditions on matrices of sign-rank 3 and unit disk graphs (UDGs) which permit constant-cost public-coin randomized communication prot…
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…
Graphs with minimum fractional domatic number
Maximilien Gadouleau, Nathaniel Harms, George B. Mertzios +1
The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant…
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…
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…
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…
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…
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 …