{"ID":2850734,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.21589","arxiv_id":"2510.21589","title":"Relative-error unateness testing","abstract":"The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider the problem of relative-error testing an unknown and arbitrary $f: \\{0,1\\}^n \\to \\{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 $\\tilde{O}(\\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 $\\tilde{O}(\\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.","short_abstract":"The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider the problem of relative-error testing an unknown and arbitrary $f: \\{0,1\\}^n \\to \\{0,1\\}$ for the property of being a unate function, i.e. a f...","url_abs":"https://arxiv.org/abs/2510.21589","url_pdf":"https://arxiv.org/pdf/2510.21589v1","authors":"[\"Xi Chen\",\"Diptaksho Palit\",\"Kabir Peshawaria\",\"William Pires\",\"Rocco A. Servedio\",\"Yiding Zhang\"]","published":"2025-10-24T15:55:05Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}