Approximating the distance to monotonicity of Boolean functions
From MaRDI portal
Recommendations
- Approximating the distance to monotonicity of Boolean functions
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Estimating the distance to a monotone function
Cited in
(15)- On an approximate computation of the height of the maximal upper zero of a monotone Boolean function
- The Boolean map distance: theory and efficient computation
- Approximating the distance to monotonicity in high dimensions
- scientific article; zbMATH DE number 7034406 (Why is no real title available?)
- scientific article; zbMATH DE number 4177135 (Why is no real title available?)
- A necessary and sufficient criterion for the monotonicity of Boolean functions with deterministic and stochastic applications
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- scientific article; zbMATH DE number 7300360 (Why is no real title available?)
- Estimating the distance to a monotone function
- scientific article; zbMATH DE number 6402335 (Why is no real title available?)
- Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
- Approximating the distance to monotonicity of Boolean functions
- scientific article; zbMATH DE number 7691481 (Why is no real title available?)
- Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
- Erasure-resilient sublinear-time graph algorithms
This page was built for publication: Approximating the distance to monotonicity of Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146909)
