Directed isoperimetric theorems for Boolean functions on the hypergrid and an O(nd) monotonicity tester

Cites work

L_p-testing
A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\)
A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
A polynomial lower bound for testing monotonicity
Adaptive Boolean Monotonicity Testing in Total Influence Time
Approximating the distance to monotonicity in high dimensions
Approximating the distance to monotonicity of Boolean functions
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
Distribution-free property testing
Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
Estimating the distance to a monotone function
scientific article; zbMATH DE number 5764799 (Why is no real title available?)
scientific article; zbMATH DE number 1775411 (Why is no real title available?)
scientific article; zbMATH DE number 1418269 (Why is no real title available?)
scientific article; zbMATH DE number 6395191 (Why is no real title available?)
Information theory in property testing and monotonicity testing in higher dimension
Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
Lower bounds for local monotonicity reconstruction from transitive-closure spanners
Monotonicity testing and shortest-path routing on the cube
Monotonicity testing over general poset domains
On disjoint chains of subsets
On Monotonicity Testing and Boolean Isoperimetric-type Theorems
On the strength of comparisons in property testing
Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
Parameterized property testing of functions
Property testing lower bounds via communication complexity
Property Testing on Product Distributions
Testing monotonicity
Testing monotonicity over graph products

Cited in

(6)

Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
Dimension-free discretizations of the uniform norm by small product sets
Testing intersecting and union-closed families
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
On the spectral expansion of monotone subsets of the hypercube

This page was built for publication: Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499226)