A polynomial lower bound for testing monotonicity
From MaRDI portal
Publication:4994983
Recommendations
- A polynomial lower bound for testing monotonicity
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- scientific article; zbMATH DE number 1418269
- A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
Cites work
- L_p-testing
- A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- A polynomial lower bound for testing monotonicity
- Adaptivity is exponentially powerful for testing monotonicity of halfspaces
- Approximation by DNF: Examples and Counterexamples
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Families of Non-disjoint subsets
- How much are increasing sets positively correlated?
- scientific article; zbMATH DE number 1819631 (Why is no real title available?)
- scientific article; zbMATH DE number 6538684 (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?)
- scientific article; zbMATH DE number 3198427 (Why is no real title available?)
- Improved approximation of linear threshold functions
- Monotonicity testing and shortest-path routing on the cube
- Monotonicity testing over general poset domains
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- On the distributional complexity of disjointness
- On the noise sensitivity of monotone functions
- Property testing lower bounds via communication complexity
- Testing Halfspaces
- Testing monotonicity
- The Chow parameters problem
- Transitive-closure spanners
Cited in
(12)- Exponentially improved algorithms and lower bounds for testing signed majorities
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- Adaptivity is exponentially powerful for testing monotonicity of halfspaces
- Adaptive lower bound for testing monotonicity on the line
- Adaptive Boolean Monotonicity Testing in Total Influence Time
- A polynomial lower bound for testing monotonicity
- scientific article; zbMATH DE number 6395191 (Why is no real title available?)
- Exponentially improved algorithms and lower bounds for testing signed majorities
- Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
- A \(d^{1/2+o(1)}\) monotonicity tester for Boolean functions on \(d\)-dimensional hypergrids
This page was built for publication: A polynomial lower bound for testing monotonicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4994983)
