The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [X. Chen et al., 2025; Chen et al., 2025; Chen et al., 2025]. In this paper we consider the problem of relative-error testing an unknown and arbitrary f: {0,1}ⁿ → {0,1} for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the n input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes Õ(log(N)/ε) samples and queries, where N = |f^{-1}(1)| is the number of satisfying assignments of the function that is being tested and the value of N is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of N and with high probability makes Õ(log(N)/ε) samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of N up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.

We initiate a systematic study of the computational complexity of property testing, focusing on the relationship between query and time complexity. While traditional work in property testing has emphasized query complexity—often via information-theoretic techniques—relatively little is known about the computational hardness of property testers. Our goal is to chart the landscape of time-query interplay and develop tools for proving time complexity lower bounds. Our first contribution is a pair of time-query hierarchy theorems for property testing. For all suitable nondecreasing functions \(q(n)\) and \(t(n)\) with \(t(n) \ge q(n)\), we construct properties with query complexity \(\tilde \Theta(q(n))\) and time complexity \(\tilde \Omega(t(n))\). Our weak hierarchy holds unconditionally, whereas the strong version—assuming the Strong Exponential Time Hypothesis— provides better control over the time complexity of the constructed properties.