An \widetildeO(n) Queries Adaptive Tester for Unateness

2016/08/08 by Subhash Khot, Khot, Subhash, Igor Shinkar +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1608.02451

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

Abstract

We present an adaptive tester for the unateness property of Boolean functions. Given a function f:\0,1\ⁿ → \0,1\ the tester makes O(n log(n)/ε) adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 if a function is ε-far from being unate.

Citations

• New algorithms and lower bounds for monotonicity testing

Cited by

• Relative-error unateness testing

Related

• A \widetildeO(n) Non-Adaptive Tester for Unateness
• Boolean Unateness Testing with \widetildeO(n^3/4) Adaptive Queries
• Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
• Relative-error unateness testing
• Testing Unateness of Real-Valued Functions