Search for: All records

Abstract: The relative-error property testing model was introduced in [Chen et al., 2024] to facilitate the study of property testing for "sparse" Boolean-valued functions, i.e. ones for which only a small fraction of all input assignments satisfy the function. In this framework, the distance from the unknown target function f that is being tested to a function g is defined as Vol(f△g)/Vol(f), where the numerator is the fraction of inputs on which f and g disagree and the denominator is the fraction of inputs that satisfy f. Recent work [Chen et al., 2026] has shown that over the Boolean domain {0,1}ⁿ, any relative-error testing algorithm for the fundamental class of {halfspaces} (i.e. linear threshold functions) must make Ω(log n) oracle calls. In this paper we complement the [Chen et al., 2026] lower bound by showing that halfspaces can be relative-error tested over ℝⁿ under the standard N(0,I_n) Gaussian distribution using a sublinear number of oracle calls - in particular, substantially fewer than would be required for learning. Our results use a wide range of tools including Hermite analysis, Gaussian isoperimetric inequalities, and geometric results on noise sensitivity and surface area. 

In thetrace reconstruction problem, an unknown source stringx∈ {0,1}ⁿis sent through a probabilisticdeletion channelthat independently deletes each bit with probability δ and concatenates the surviving bits, yielding atraceofx. The problem is to reconstructxgiven independent traces. This problem has received much attention in recent years both in the worst-case setting wherexmay be an arbitrary string in {0,1}ⁿ[7,8,10,11,12,23] and in the average-case setting wherexis drawn uniformly at random from {0,1}ⁿ[7,8,12,13,25]. This article studies trace reconstruction in thesmoothed analysissetting, in which a “worst-case” stringx^worstis chosen arbitrarily from {0,1}ⁿ, and then a perturbed versionxofx^worstis formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstructxgiven independent traces from it. Our main result is an algorithm that, for any constant perturbation rate 0< σ < 1 and any constant deletion rate 0 < δ < 1, uses poly(n) running time and traces and succeeds with high probability in reconstructing the stringx. This stands in contrast with the worst-case version of the problem, for which\(\text{exp}(\tilde{O}(n^{1/5}))\)is the best known time and sample complexity [8]. Our approach is based on reconstructingxfrom the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly(n)-time procedure for reconstructing the multiset of allO(logn)-length subwords of any source stringx∈ {0,1}ⁿgiven access to traces ofx.