An ~O(n) Queries Adaptive Tester for Unateness

DOI10.4230/LIPIcs.APPROX-RANDOM.2016.37zbMath1398.68654arXiv1608.02451OpenAlexW2572640849MaRDI QIDQ4636470

Subhash A. Khot, Igor Shinkar

Publication date: 19 April 2018

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

zbMATH Keywords

Boolean functionsproperty testingunateness

Mathematics Subject Classification ID

Boolean functions (06E30) Randomized algorithms (68W20)

Related Items (7)

Approximating the distance to monotonicity of Boolean functions ⋮ Unnamed Item ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Almost Optimal Testers for Concise Representations. ⋮ Unnamed Item ⋮ Almost optimal distribution-free junta testing ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity

This page was built for publication: An ~O(n) Queries Adaptive Tester for Unateness