Testing monotonicity over graph products
From MaRDI portal
Publication:3522829
DOI10.1002/rsa.20211zbMath1156.68507MaRDI QIDQ3522829
Shirley Halevy, Eyal Kushilevitz
Publication date: 4 September 2008
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20211
68Q25: Analysis of algorithms and problem complexity
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science
68T10: Pattern recognition, speech recognition
Related Items
Unnamed Item, Erasure-Resilient Property Testing, Parameterized property testing of functions, Unnamed Item, Local Property Reconstruction and Monotonicity, Unnamed Item, Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, Approximating the distance to monotonicity of Boolean functions, Almost Optimal Distribution-Free Sample-Based Testing of k-Modality, Testing Lipschitz functions on hypergrid domains, Monotonicity testing and shortest-path routing on the cube, Exponentially improved algorithms and lower bounds for testing signed majorities, An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
Cites Work
