Improved testing algorithms for monotonicity
From MaRDI portal
Recommendations
- Testing monotonicity
- Testing k-monotonicity
- Logic Programming
- Monotonicity Analysis Can Speed Up Verification
- Monotonicity Checking
- Monotonicity checking
- An optimal lower bound for monotonicity testing over hypergrids
- scientific article; zbMATH DE number 6395191
- Automata, Languages and Programming
- Testing monotonicity over graph products
Cited in
(70)- Fast approximate PCPs for multidimensional bin-packing problems
- On the strength of comparisons in property testing
- Monotonicity properties of multiple endpoint testing procedures
- Exponentially improved algorithms and lower bounds for testing signed majorities
- Testing of matrix-poset properties
- Static extensivity analysis for \(\lambda\)-definable functions over lattices
- Tolerant property testing and distance approximation
- Checking if there exist a monotonic function that is consistent with the measurements: an efficient algorithm
- Testing Lipschitz functions on hypergrid domains
- An o(n) monotonicity tester for Boolean functions over the hypercube
- Testing Monotone Read-Once Functions
- Monotonicity checking
- Testing monotonicity over graph products
- Steiner transitive-closure spanners of low-dimensional posets
- Improved algorithms for chemical threshold testing problems
- On Testing Convexity and Submodularity
- Functions that have read‐twice constant width branching programs are not necessarily testable
- Monotonicity testing and shortest-path routing on the cube
- Testing properties of directed graphs: acyclicity and connectivity*
- Testing for forbidden order patterns in an array
- Erasure-Resilient Property Testing
- Parameterized property testing of functions
- Testing k-monotonicity
- Is submodularity testable?
- Transitive-closure spanners: a survey
- Invariance in property testing
- Local property reconstruction and monotonicity
- Parameterized property testing of functions
- A polynomial lower bound for testing monotonicity
- Adaptivity is exponentially powerful for testing monotonicity of halfspaces
- Testing hereditary properties of sequences
- Adaptive lower bound for testing monotonicity on the line
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Adaptive Boolean Monotonicity Testing in Total Influence Time
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Earthmover Resilience and Testing in Ordered Structures
- Testing for forbidden order patterns in an array
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- A polynomial lower bound for testing monotonicity
- Estimating the distance to a monotone function
- Monotonicity Analysis Can Speed Up Verification
- Automata, Languages and Programming
- scientific article; zbMATH DE number 6395191 (Why is no real title available?)
- Monotonicity Checking
- Estimating the longest increasing sequence in polylogarithmic time
- Testing monotonicity
- Testing juntas
- Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
- Approximating the distance to monotonicity of Boolean functions
- Improved algorithm for permutation testing
- Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
- Strongly sublinear algorithms for testing pattern freeness
- Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
- The power and limitations of uniform samples in testing properties of figures
- Testing intersecting and union-closed families
- Property testing with online adversaries
- Nearly optimal bounds for sample-based testing and learning of k-monotone functions
- Property testing lower bounds via communication complexity
- Approximation algorithms for LCS and LIS with truly improved running times
- Property testing with online adversaries
- Agnostic proper learning of monotone functions: beyond the black-box correction barrier
- A \(d^{1/2+o(1)}\) monotonicity tester for Boolean functions on \(d\)-dimensional hypergrids
- Directed hypercube routing, a generalized Lehman-Ron theorem, and monotonicity testing
- Online versus offline adversaries in property testing
- Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)
- The trichotomy of regular property testing
- Information theory in property testing and monotonicity testing in higher dimension
- Distribution-free connectivity testing for sparse graphs
- Testing whether a digraph contains H-free k-induced subgraphs
This page was built for publication: Improved testing algorithms for monotonicity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4941829)
