Nathaniel Harms

STOC Conference 2025 Conference Paper

Constant-Cost Communication Is Not Reducible to k-Hamming Distance

• Yuting Fang
• Mika Göös
• Nathaniel Harms
• Pooya Hatami

Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to k -Hamming Distance, that is, solved with a constant number of deterministic queries to some k -Hamming Distance oracle. We exhibit the first examples of constant-cost problems which cannot be reduced to k -Hamming Distance. To prove this separation, we relate it to a natural coding-theoretic question. For f ∶ {2,4,6}→ℕ, we say that an encoding function E ∶{0,1} n →{0,1} m is an f -code if it transforms Hamming distances according to dist ( E ( x ), E ( y ))= f ( dist ( x , y )) whenever f is defined. We prove that, if there exist f -codes for infinitely many n , then f must be affine: f (4)=( f (2)+ f (6))/2.

FOCS Conference 2025 Conference Paper

Sign-Rank of k-Hamming Distance is Constant

• Mika Göös
• Nathaniel Harms
• Valentin Imbach
• Dmitry Sokolov 0001

We prove that the sign-rank of the k Hamming Distance matrix on n bits is $2^{O(k)}$, independent of the number of bits n. This strongly refutes the conjecture of Hatami, Hatami, Pires, Tao, and Zhao (random 2022), and Hatami, Hosseini, and Meng (STOC 2023), repeated in several other papers, that the sign-rank should depend on n. This conjecture would have qualitatively separated margin from sign-rank (or, equivalently, bounded-error from unbounded-error randomized communication). In fact, our technique gives constant sign-rank upper bounds for all matrices which reduce to k-Hamming Distance, as well as large-margin matrices recently shown to be irreducible to k-Hamming Distance.

STOC Conference 2025 Conference Paper

Testing Support Size More Efficiently Than Learning Histograms

• Renato Ferreira Pinto Jr.
• Nathaniel Harms

Consider two problems about an unknown probability distribution p : (1) How many samples from p are required to test if p is supported on n elements or not? Specifically, given samples from p , determine whether it is supported on at most n elements, or it is ”є-far” (in total variation distance) from being supported on n elements. (2) Given m samples from p , what is the largest lower bound on its support size that we can produce? The best known upper bound for problem (1) uses a general algorithm for learning the histogram of the distribution p , which requires Θ( n /є 2 log n ) samples. We show that testing can be done more efficiently than learning the histogram, using only O ( n /є log n log(1/є)) samples, nearly matching the best known lower bound of Ω( n /є log n ). This algorithm also provides a better solution to problem (2), producing larger lower bounds on support size than what follows from previous work. The proof relies on an analysis of Chebyshev polynomial approximations outside the range where they are designed to be good approximations.

STOC Conference 2024 Conference Paper

No Complete Problem for Constant-Cost Randomized Communication

• Yuting Fang
• Lianna Hambardzumyan
• Nathaniel Harms
• Pooya Hatami

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called BPP 0 , does not contain a complete problem. In other words, there is no randomized constant-cost problem Q ∈ BPP 0 , such that all other problems P ∈ BPP 0 can be computed by a constant-cost deterministic protocol with access to an oracle for Q . We also show that the k -Hamming Distance problems form an infinite hierarchy within BPP 0 . Previously, it was known only that Equality is not complete for BPP 0 . We introduce a new technique, using Ramsey theory, that can prove lower bounds against arbitrary oracles in BPP 0 , and more generally, we show that k -Hamming Distance matrices cannot be expressed as a Boolean combination of any constant number of matrices which forbid large Greater-Than subproblems.

SODA Conference 2024 Conference Paper

Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank

• Nathaniel Harms
• Viktor Zamaraev

STOC Conference 2022 Conference Paper

Randomized communication and implicit graph representations

• Nathaniel Harms
• Sebastian Wild
• Viktor Zamaraev

The most basic lower-bound question in randomized communication complexity is: Does a given problem have constant cost, or non-constant cost? We observe that this question has a deep connection to implicit graph representations in structural graph theory. Specifically, constant-cost communication problems correspond to hereditary graph families that admit constant-size adjacency sketches, or equivalently constant-size probabilistic universal graphs (PUGs), and these graph families are a subset of families that admit adjacency labeling schemes of size O (log n ), which are the subject of the well-studied implicit graph question (IGQ).

STOC Conference 2021 Conference Paper

VC dimension and distribution-free sample-based testing

• Eric Blais
• Renato Ferreira Pinto Jr.
• 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 corresponds to the standard PAC learning setting. Our main result shows that while VC dimension by itself does not always provide tight bounds on the number of samples required to test a class of functions in this model, it can be combined with a closely-related variant that we call “lower VC” (or LVC) dimension to obtain strong lower bounds on this sample complexity. We use this result to obtain strong and in many cases nearly optimal bounds on the sample complexity for testing unions of intervals, halfspaces, intersections of halfspaces, polynomial threshold functions, and decision trees. Conversely, we show that two natural classes of functions, juntas and monotone functions, can be tested with a number of samples that is polynomially smaller than the number of samples required for PAC learning. Finally, we also use the connection between VC dimension and property testing to establish new lower bounds for testing radius clusterability and testing feasibility of linear constraint systems.

SODA Conference 2019 Conference Paper

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 f, the algorithm determines with high probability whether f is of the form f ( x ) = sign(∑ i ω i x i – t ) or is ∊-far from all such functions. This sample size is significantly smaller than the well-known requirement of Θ( n ) samples for learning halfspaces, and known lower bounds imply that our sample size is optimal (in its dependence on n ) up to logarithmic factors. The algorithm is distribution-free in the sense that it requires no knowledge of the distribution aside from the promise of rotation invariance. To prove the correctness of this algorithm we present a theorem relating the distance between a function and a halfspace to the distance between their centers of mass, that applies to arbitrary distributions.