On the strength of comparisons in property testing

DOI10.1016/J.IC.2003.09.003MaRDI QIDQ1887149zbMATH OpenOpenAlexFDO

Authors Eldar Fischer

Publication date 23 November 2004

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2003.09.003

zbMATH Keywords

MonotonicityProperty testingRamsey's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20)

Recommendations

• Adaptive lower bound for testing monotonicity on the line
• scientific article; zbMATH DE number 1418269
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Testing for forbidden order patterns in an array
• Testing for forbidden order patterns in an array

Cites work

• Efficient testing of large graphs
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 46958 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• Monotonicity testing over general poset domains
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Regular languages are testable with a constant number of queries
• Robust Characterizations of Polynomials with Applications to Program Testing
• Spot-checkers
• Testing monotonicity
• Transforming comparison model lower bounds to the parallel-random-access-machine

Cited in

(36)

• Testing of matrix-poset properties
• Tolerant property testing and distance approximation
• Monotonicity testing and shortest-path routing on the cube
• Testing for forbidden order patterns in an array
• Improved bounds for testing forbidden order patterns
• Erasure-Resilient Property Testing
• Parameterized property testing of functions
• Testing k-monotonicity
• Is submodularity testable?
• Property testing of massively parametrized problems -- a survey
• Transitive-closure spanners: a survey
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Local property reconstruction and 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
• Testing local properties of arrays
• Earthmover Resilience and Testing in Ordered Structures
• Optimal unateness testers for real-valued functions: adaptivity helps
• Testing of matrix properties
• Testing for forbidden order patterns in an array
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• On the benefits of adaptivity in property testing of dense graphs
• 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
• Nearly optimal bounds for sample-based testing and learning of k-monotone functions
• Property testing with online adversaries
• New sublinear algorithms and lower bounds for LIS estimation
• A \(d^{1/2+o(1)}\) monotonicity tester for Boolean functions on \(d\)-dimensional hypergrids
• Information theory in property testing and monotonicity testing in higher dimension
• Distribution-free connectivity testing for sparse graphs

This page was built for publication: On the strength of comparisons in property testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1887149)