Adaptive Boolean Monotonicity Testing in Total Influence Time
From MaRDI portal
Recommendations
- A polynomial lower bound for testing monotonicity
- A polynomial lower bound for testing monotonicity
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
Cites work
- A polynomial lower bound for testing monotonicity
- An o(n) monotonicity tester for Boolean functions over the hypercube
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- scientific article; zbMATH DE number 1418269 (Why is no real title available?)
- Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
- Monotonicity testing over general poset domains
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Parameterized property testing of functions
- Testing monotonicity
Cited in
(6)- Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
- Approximating the distance to monotonicity of Boolean functions
- Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
- Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
- Testing intersecting and union-closed families
- Agnostic proper learning of monotone functions: beyond the black-box correction barrier
This page was built for publication: Adaptive Boolean Monotonicity Testing in Total Influence Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090393)
