Testing unateness nearly optimally

DOI10.1145/3313276.3316351MaRDI QIDQ5212796zbMATH OpenOpenAlexFDO

Authors Xi Chen, Erik Waingarten

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.05309

zbMATH Keywords

Boolean functionsproperty testingunateness

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Abstract: We present an $ildeO(n^{2/3}/epsilo{n}^2)$-query algorithm that tests whether an unknown Boolean function $fcolon{0,1}^{n}ightarrow0,1$ is unate (i.e., every variable is either non-decreasing or non-increasing) or $epsilon$-far from unate. The upper bound is nearly optimal given the $ildeOmega(n^{2/3})$ lower~bound of [CWX17a]. The algorithm builds on a novel use of the binary search procedure and its analysis over long random paths.

Recommendations

• An O(n) queries adaptive tester for unateness
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Optimal unateness testers for real-valued functions: adaptivity helps
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• Optimal unateness testers for real-valued functions: Adaptivity helps

Cited in

(10)

• The forbidden projections of unate functions
• Input-Thrifty Extrema Testing
• An O(n) queries adaptive tester for unateness
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Optimal unateness testers for real-valued functions: Adaptivity helps
• Optimal unateness testers for real-valued functions: adaptivity helps
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Approximating the distance to monotonicity of Boolean functions
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier

This page was built for publication: Testing unateness nearly optimally

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212796)