4 citations · 5 across the 6 of their papers we have counts for
4 papers · 1 filter
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…