For a function \(f : \{0, 1\}^n \rightarrow \{0, 1\}\), the junta testing problem asks whether \(f\) depends on only \(k\) variables. If \(f\) depends on only \(k\) variables, the feature selection problem asks to find those variables. We prove that these two tasks are statistically equivalent. Specifically, we show that the “brute-force” algorithm, which checks for any set of \(k\) variables consistent with the sample, is simultaneously sample-optimal for both problems, and the optimal sample size is \begin{align} \Theta\left( \frac{1}{\varepsilon} \left(\sqrt{2^{k} \log\binom{n}{k}} + \log\binom{n}{k} \right) \right).\end{align}

We exhibit an n-bit partial function with randomized communication complexity O(logn) but such that any completion of this function into a total one requires randomized communication complexity nΩ(1). In particular, this shows an exponential separation between randomized and pseudodeterministic communication protocols. Previously, Gavinsky (2025) showed an analogous separation in the weaker model of parity decision trees. We use lifting techniques to extend his proof idea to communication complexity.

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.

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

Consider two problems about an unknown probability distribution 𝑝: (1) How many samples from 𝑝 are required to test if 𝑝 is supported on 𝑛 elements or not? Specifically, given samples from 𝑝, determine whether it is supported on at most 𝑛 elements, or it is “𝜀-far” (in total variation distance) from being supported on 𝑛 elements. (2) Given𝑚 samples from 𝑝, 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 𝑝, which requires Θ( 𝑛 𝜀2 log𝑛) samples .We showthat testing can be done more efficiently than learning the histogram, using only𝑂( 𝑛 𝜀 log𝑛 log(1/𝜀)) samples, nearly matching the best known lower bound of Ω( 𝑛 𝜀 log𝑛). 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.

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\} \to \mathbb{N}$, we say an encoding function $E : \{0, 1\}^n \to \{0, 1\}^m$ is an $f$-code if it transforms Hamming distances according to $\mathrm{dist}(E(x), E(y)) = f(\mathrm{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$.

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 ternary hypercube, {-1,0,1}ⁿ. The goal of this work is to understand structural combinatorial properties of convex sets in this domain and to determine the complexity of the testing and learning problems. We obtain the following results. Structural: We prove nearly tight bounds on the edge boundary of convex sets in {0,±1}ⁿ, showing that the maximum edge boundary of a convex set is Õ(n^{3/4})⋅3ⁿ, or equivalently that every convex set has influence Õ(n^{3/4}) and a convex set exists with influence Ω(n^{3/4}). Learning and sample-based testing: We prove upper and lower bounds of 3^{Õ(n^{3/4})} and 3^{Ω(√n)} for the task of learning convex sets under the uniform distribution from random examples. The analysis of the learning algorithm relies on our upper bound on the influence. Both the upper and lower bound also hold for the problem of sample-based testing with two-sided error. For sample-based testing with one-sided error we show that the sample-complexity is 3^{Θ(n)}. Testing with queries: We prove nearly matching upper and lower bounds of 3^{Θ̃(√n)} for one-sided error testing of convex sets with non-adaptive queries.

We are interested in testing properties of distributions with systematically mislabeled samples. Our goal is to make decisions about unknown probability distributions, using a sample that has been collected by a confused collector, such as a machine-learning classifier that has not learned to distinguish all elements of the domain. The confused collector holds an unknown clustering of the domain and an input distribution μ, and provides two oracles: a sample oracle which produces a sample from μ that has been labeled according to the clustering; and a label-query oracle which returns the label of a query point x according to the clustering. Our first set of results shows that identity, uniformity, and equivalence of distributions can be tested efficiently, under the earth-mover distance, with remarkably weak conditions on the confused collector, even when the unknown clustering is adversarial. This requires defining a variant of the distribution testing task (inspired by the recent testable learning framework of Rubinfeld & Vasilyan), where the algorithm should test a joint property of the distribution and its clustering. As an example, we get efficient testers when the distribution tester is allowed to reject if it detects that the confused collector clustering is "far" from being a decision tree. The second set of results shows that we can sometimes do significantly better when the clustering is random instead of adversarial. For certain one-dimensional random clusterings, we show that uniformity can be tested under the TV distance using Õ((√n)/(ρ^{3/2} ε²)) samples and zero queries, where ρ ∈ (0,1] controls the "resolution" of the clustering. We improve this to O((√n)/(ρ ε²)) when queries are allowed.

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 protocols. Therefore, under these conditions, these graphs also admit implicit representations.

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called BPP0, does not contain a complete problem. In other words, there is no randomized constant-cost problem Q ∈ BPP0, such that all other problems P ∈ BPP0 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 BPP0. Previously, it was known only that Equality is not complete for BPP0. We introduce a new technique, using Ramsey theory, that can prove lower bounds against arbitrary oracles in BPP0, 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.

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 of this notion. Graphs with fractional domatic number 1 are exactly the graphs that contain an isolated vertex. Furthermore, it is known that all other graphs have fractional domatic number at least 2. In this note we characterize graphs with fractional domatic number 2. More specifically, we show that a graph without isolated vertices has fractional domatic number 2 if and only if it has a vertex of degree 1 or a connected component isomorphic to a 4-cycle. We conjecture that if the fractional domatic number is more than 2, then it is at least 7/3.

Abstract. For any hereditary graph class [Formula: see text], we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in [Formula: see text]. As a consequence, we show that if [Formula: see text] admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then so do the classes of subgraphs and induced subgraphs of Cartesian products of graphs in [Formula: see text]. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics and improves upon recent results of Chepoi, Labourel, and Ratel [ J. Graph Theory, 93 (2020), pp. 64–87].

For any hereditary graph class $F$, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in $F$. As a consequence, we show that, if $F$ admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then the classes of subgraphs and induced subgraphs of Cartesian products of graphs in $F$ do too. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics, and improves upon recent results of Chepoi, Labourel, and Ratel [Journal of Graph Theory, 2020].

We study the two-player communication problem of determining whether two vertices $x, y$ are nearby in a graph $G$, with the goal of determining the graph structures that allow the problem to be solved with a constant-cost randomized protocol. Equivalently, we consider the problem of assigning constant-size random labels (sketches) to the vertices of a graph, which allow adjacency, exact distance thresholds, or approximate distance thresholds to be computed with high probability from the labels. Our main results are that, for monotone classes of graphs: constant-size adjacency sketches exist if and only if the class has bounded arboricity; constant-size sketches for exact distance thresholds exist if and only if the class has bounded expansion; constant-size approximate distance threshold (ADT) sketches imply that the class has bounded expansion; any class of constant expansion (i.e. any proper minor closed class) has constant-size ADT sketches; and a class may have arbitrarily small expansion without admitting constant-size ADT sketches.

We study distribution-free property testing and learning problems where the unknown probability distribution is a product distribution over $\mathbb{R}^d$. For many important classes of functions, such as intersections of halfspaces, polynomial threshold functions, convex sets, and $k$-alternating functions, the known algorithms either have complexity that depends on the support size of the distribution, or are proven to work only for specific examples of product distributions. We introduce a general method, which we call downsampling, that resolves these issues. Downsampling uses a notion of "rectilinear isoperimetry" for product distributions, which further strengthens the connection between isoperimetry, testing, and learning. Using this technique, we attain new efficient distribution-free algorithms under product distributions on $\mathbb{R}^d$: 1. A simpler proof for non-adaptive, one-sided monotonicity testing of functions $[n]^d \to \{0,1\}$, and improved sample complexity for testing monotonicity over unknown product distributions, from $O(d^7)$ [Black, Chakrabarty, & Seshadhri, SODA 2020] to $\widetilde O(d^3)$. 2. Polynomial-time agnostic learning algorithms for functions of a constant number of halfspaces, and constant-degree polynomial threshold functions. 3. An $\exp(O(d \log(dk)))$-time agnostic learning algorithm, and an $\exp(O(d \log(dk)))$-sample tolerant tester, for functions of $k$ convex sets; and a $2^{\widetilde O(d)}$ sample-based one-sided tester for convex sets. 4. An $\exp(\widetilde O(k \sqrt d))$-time agnostic learning algorithm for $k$-alternating functions, and a sample-based tolerant tester with the same complexity.

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(logn), which are the subject of the well-studied implicit graph question (IGQ).

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 introduce a communication model called universal SMP, in which Alice and Bob receive a function $f$ belonging to a family $\mathcal{F}$, and inputs $x$ and $y$. Alice and Bob use shared randomness to send a message to a third party who cannot see $f, x, y$, or the shared randomness, and must decide $f(x,y)$. Our main application of universal SMP is to relate communication complexity to graph labeling, where the goal is to give a short label to each vertex in a graph, so that adjacency or other functions of two vertices $x$ and $y$ can be determined from the labels $\ell(x),\ell(y)$. We give a universal SMP protocol using $O(k^2)$ bits of communication for deciding whether two vertices have distance at most $k$ on distributive lattices (generalizing the $k$-Hamming Distance problem in communication complexity), and explain how this implies an $O(k^2\log n)$ labeling scheme for determining $\mathrm{dist}(x,y) \leq k$ on distributive lattices with size $n$; in contrast, we show that a universal SMP protocol for determining $\mathrm{dist}(x,y) \leq 2$ in modular lattices (a superset of distributive lattices) has super-constant $Ω(n^{1/4})$ communication cost. On the other hand, we demonstrate that many graph families known to have efficient adjacency labeling schemes, such as trees, low-arboricity graphs, and planar graphs, admit constant-cost communication protocols for adjacency. Trees also have an $O(k)$ protocol for deciding $\mathrm{dist}(x,y) \leq k$ and planar graphs have an $O(1)$ protocol for $\mathrm{dist}(x,y) \leq 2$, which implies a new $O(\log n)$ labeling scheme for the same problem on planar graphs.

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 ωixi – 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.