Testing monotonicity over graph products

DOI10.1002/rsa.20211zbMath1156.68507OpenAlexW4249956697MaRDI 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

zbMATH Keywords

graph productsproperty testingmonotonicity testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10)

Related Items (14)

Testing Lipschitz functions on hypergrid domains ⋮ Parameterized property testing of functions ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Monotonicity testing and shortest-path routing on the cube ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Local Property Reconstruction and Monotonicity ⋮ An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube ⋮ Unnamed Item ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities

Cites Work

• Monotonicity testing over general poset domains
• Testing of matrix properties

This page was built for publication: Testing monotonicity over graph products