Adaptive Boolean Monotonicity Testing in Total Influence Time

DOI10.4230/LIPIcs.ITCS.2019.20OpenAlexW2963889436MaRDI QIDQ5090393

Deeparnab Chakrabarty, C. Seshadhri

Publication date: 18 July 2022

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

zbMATH Keywords

property testingmonotonicity testinginfluence of Boolean functions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Approximating the distance to monotonicity of Boolean functions, Almost Optimal Distribution-Free Sample-Based Testing of k-Modality

Cites Work

• Unnamed Item
• Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
• An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
• Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
• Monotonicity testing over general poset domains
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Parameterized property testing of functions
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• A polynomial lower bound for testing monotonicity
• Testing monotonicity