Monotonicity testing over general poset domains
DOI10.1145/509907.509977zbMATH Open1192.68359OpenAlexW2038521541MaRDI QIDQ3579209FDOQ3579209
Authors: Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky 
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30)
Cited In (46)
- An algebraic characterization of testable Boolean CSPs
- Adaptive Boolean Monotonicity Testing in Total Influence Time
- Adaptivity is exponentially powerful for testing monotonicity of halfspaces
- Sparse hypergraphs with applications to coding theory
- Almost optimal distribution-free junta testing
- Erasure-Resilient Property Testing
- Testing Lipschitz functions on hypergrid domains
- Testing convexity properties of tree colorings
- Testing juntas
- Is submodularity testable?
- Testing \(k\)-monotonicity
- An \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- Constant-query testability of assignments to constraint satisfaction problems
- Tolerant property testing and distance approximation
- Transitive-closure spanners: a survey
- Lower Bounds for Testing Computability by Small Width OBDDs
- Local property reconstruction and monotonicity
- Monotonicity testing and shortest-path routing on the cube
- Fast approximate PCPs for multidimensional bin-packing problems
- Exponentially improved algorithms and lower bounds for testing signed majorities
- A characterization of constant-sample testable properties
- Property testing lower bounds via communication complexity
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Information theory in property testing and monotonicity testing in higher dimension
- Approximating the distance to monotonicity of Boolean functions
- Title not available (Why is that?)
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
- Testing Euclidean Spanners
- A large lower bound on the query complexity of a simple Boolean function
- Estimating the longest increasing sequence in polylogarithmic time
- Testing list \(H\)-homomorphisms
- Parameterized property testing of functions
- On the strength of comparisons in property testing
- Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
- On regularity lemma and barriers in streaming and dynamic matching
- Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
- Distribution-free connectivity testing for sparse graphs
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Testing monotonicity over graph products
- Adaptive lower bound for testing monotonicity on the line
- Testing of matrix-poset properties
- A polynomial lower bound for testing monotonicity
- The power and limitations of uniform samples in testing properties of figures
- Colorings with only rainbow arithmetic progressions
- Property testing of massively parametrized problems -- a survey
This page was built for publication: Monotonicity testing over general poset domains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579209)
