Testing monotonicity over graph products
From MaRDI portal
Recommendations
- Automata, Languages and Programming
- A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\)
- scientific article; zbMATH DE number 1418269
- Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
- An optimal lower bound for monotonicity testing over hypergrids
Cited in
(20)- Exponentially improved algorithms and lower bounds for testing signed majorities
- Testing Lipschitz functions on hypergrid domains
- An o(n) monotonicity tester for Boolean functions over the hypercube
- Monotonicity testing and shortest-path routing on the cube
- Erasure-Resilient Property Testing
- Parameterized property testing of functions
- Testing k-monotonicity
- Local property reconstruction and monotonicity
- scientific article; zbMATH DE number 1418269 (Why is no real title available?)
- Adaptivity is exponentially powerful for testing monotonicity of halfspaces
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Optimal unateness testers for real-valued functions: adaptivity helps
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Automata, Languages and Programming
- 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
- Nearly optimal bounds for sample-based testing and learning of k-monotone functions
- A \(d^{1/2+o(1)}\) monotonicity tester for Boolean functions on \(d\)-dimensional hypergrids
This page was built for publication: Testing monotonicity over graph products
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3522829)
