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.

Several recent works (Chen et al., SODA 2025; Chen et al., ICALP 2025; Chen et al., COLT 2025; Chen et al., manuscript) have studied a model of property testing of Boolean functions under a relative-error criterion. In this model, the distance from a target function \(f : \{0, 1\}^n \rightarrow \{0, 1\}\) that is being tested to a function \(g\) is defined relative to the number of inputs \(x\) for which \(f(x) = 1\); moreover, testing algorithms in this model have access both to a black-box oracle for \(f\) and to independent uniform satisfying assignments of \(f\). The motivation for this model is that it provides a natural framework for testing sparse Boolean functions that have few satisfying assignments, analogous to well-studied models for property testing of sparse graphs.

The standard model of Boolean function property testing is not well suited for testing sparse functions which have few satisfying assignments, since every such function is close (in the usual Hamming distance metric) to the constant-0 function. In this work we propose and investigate a new model for property testing of Boolean functions, called relative-error testing, which provides a natural framework for testing sparse functions.

Investigating the computational resources we need for cryptography is an essential task of both theoretical and practical interests. This paper provides answers to this problem on pseudorandom functions (PRFs). We resolve the exact complexity of PRFs by proving tight upper and lower bounds for various circuit models.

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although it can be shown that almost every function f:F2n→F2 requires circuit of size Ω(2n/n) by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in NP) not computable by circuits of size 10n. In fact, a 3n−o(n) explicit lower bound by Blum (TCS, 1984) was unbeaten for over 30 years until a recent breakthrough by Find, Golovnev, Hirsch, and Kulikov (FOCS, 2016), which proved a (3+1/86)n−o(n) lower bound for affine dispersers, a class of functions known to be constructible in P. To obtain this improvement, Find, Golovnev, Hirsch, and Kulikov (FOCS, 2016) generalized the classical gate elimination method by keeping track of a bottleneck structure called troubled gates.