Monotonicity testing over general poset domains

DOI10.1145/509907.509977zbMath1192.68359OpenAlexW2038521541MaRDI QIDQ3579209

Eric Lehman, Ilan Newman, Alex Samorodnitsky, Eldar Fischer, Ronitt Rubinfeld, Sofya Raskhodnikova

Publication date: 5 August 2010

Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/509907.509977

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Boolean functions (06E30) Randomized algorithms (68W20)

Related Items

Testing Lipschitz functions on hypergrid domains, On the strength of comparisons in property testing, Parameterized property testing of functions, Information theory in property testing and monotonicity testing in higher dimension, Testing list \(H\)-homomorphisms, On Monotonicity Testing and Boolean Isoperimetric-type Theorems, Testing juntas, An Algebraic Characterization of Testable Boolean CSPs, Approximating the distance to monotonicity of Boolean functions, Unnamed Item, Erasure-Resilient Property Testing, Testing monotonicity over graph products, Monotonicity testing and shortest-path routing on the cube, Sparse Hypergraphs with Applications to Coding Theory, Distribution-free connectivity testing for sparse graphs, Colorings with only rainbow arithmetic progressions, Is submodularity testable?, Testing Euclidean Spanners, The power and limitations of uniform samples in testing properties of figures, 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, Property testing lower bounds via communication complexity, Estimating the Longest Increasing Sequence in Polylogarithmic Time, Testing convexity properties of tree colorings, Fast approximate PCPs for multidimensional bin-packing problems, Property Testing of Massively Parametrized Problems – A Survey, Transitive-Closure Spanners: A Survey, Local Property Reconstruction and Monotonicity, Tolerant property testing and distance approximation, An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube, Adaptive Boolean Monotonicity Testing in Total Influence Time, Almost optimal distribution-free junta testing, Constant-Query Testability of Assignments to Constraint Satisfaction Problems, A characterization of constant‐sample testable properties, A Polynomial Lower Bound for Testing Monotonicity, A large lower bound on the query complexity of a simple Boolean function, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, Unnamed Item, Unnamed Item, Exponentially improved algorithms and lower bounds for testing signed majorities