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

Ramsey's theoremMonotonicityProperty testing

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

• 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?)
• Efficient testing of large graphs
• 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

(32)

• Property testing of massively parametrized problems -- a survey
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• scientific article; zbMATH DE number 7559054 (Why is no real title available?)
• Improved algorithm for permutation testing
• Erasure-Resilient Property Testing
• Optimal unateness testers for real-valued functions: adaptivity helps
• Strongly sublinear algorithms for testing pattern freeness
• Is submodularity testable?
• Testing for forbidden order patterns in an array
• Testing \(k\)-monotonicity
• Tolerant property testing and distance approximation
• Earthmover Resilience and Testing in Ordered Structures
• Transitive-closure spanners: a survey
• Monotonicity testing and shortest-path routing on the cube
• Local property reconstruction and monotonicity
• On the benefits of adaptivity in property testing of dense graphs
• Improved bounds for testing forbidden order patterns
• Information theory in property testing and monotonicity testing in higher dimension
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Approximating the distance to monotonicity of Boolean functions
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Parameterized property testing of functions
• Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
• Testing hereditary properties of sequences
• 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 for forbidden order patterns in an array
• Adaptive lower bound for testing monotonicity on the line
• Testing of matrix-poset properties
• Testing of matrix properties

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)