A \widetildeO(n) Non-Adaptive Tester for Unateness

2016/08/24 by Deeparnab Chakrabarty, Chakrabarty, Deeparnab, C. Seshadhri +1
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning and Algorithms #Software Testing and Debugging Techniques

paper · pdf · doi:10.48550/arxiv.1608.06980

openalex publication_date 2016/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, O(n log(n)/ε)-query tester for unateness of Boolean functions f:\0,1\ⁿ → \0,1\. In this note we describe a simple non-adaptive, O(n log(n/ε)/ε) -query tester for unateness for functions over the hypercube with any ordered range.

Related

• An \widetildeO(n) Queries Adaptive Tester for Unateness
• Boolean Unateness Testing with \widetildeO(n^3/4) Adaptive Queries
• Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
• A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube
• Testing Unateness of Real-Valued Functions