Testing monotonicity

DOI10.1007/S004930070011zbMath0964.68148OpenAlexW4235805661MaRDI QIDQ5932642

Dana Ron, Oded Goldreich, Alex Samorodnitsky, Eric Lehman

Publication date: 12 June 2001

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004930070011

zbMATH Keywords

learning randomized algorithmsmonotone Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Randomized algorithms (68W20)

Related Items (53)

Testing Lipschitz functions on hypergrid domains ⋮ On the strength of comparisons in property testing ⋮ Parameterized property testing of functions ⋮ Applying cube attacks to stream ciphers in realistic scenarios ⋮ A lower bound for testing juntas ⋮ Information theory in property testing and monotonicity testing in higher dimension ⋮ A quantitative Gobbard-Satterthwaite theorem without neutrality ⋮ On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ Testing juntas ⋮ Sorting with forbidden intermediates ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ An optimal tester for \(k\)-Linear ⋮ Hierarchy theorems for property testing ⋮ Unnamed Item ⋮ An Inequality for Functions on the Hamming Cube ⋮ Erasure-Resilient Property Testing ⋮ Monotonicity testing and shortest-path routing on the cube ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Is submodularity testable? ⋮ Testing Euclidean Spanners ⋮ Hierarchy Theorems for Property Testing ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Sample-Based High-Dimensional Convexity Testing. ⋮ Testing of matrix-poset properties ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs ⋮ Almost Optimal Testers for Concise Representations. ⋮ Property testing lower bounds via communication complexity ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time ⋮ On disjoint chains of subsets ⋮ Attribute estimation and testing quasi-symmetry ⋮ Transitive-Closure Spanners: A Survey ⋮ Invariance in Property Testing ⋮ Local Property Reconstruction and Monotonicity ⋮ A non-extendibility certificate for submodularity and applications ⋮ Unnamed Item ⋮ Testing piecewise functions ⋮ Tolerant property testing and distance approximation ⋮ An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube ⋮ A linear fit gets the correct monotonicity directions ⋮ On the Average-Case Complexity of Property Testing ⋮ Adaptive Boolean Monotonicity Testing in Total Influence Time ⋮ Almost optimal distribution-free junta testing ⋮ A characterization of constant‐sample testable properties ⋮ Unnamed Item ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item ⋮ Monotonicity checking ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities

This page was built for publication: Testing monotonicity