On the strength of comparisons in property testing

DOI10.1016/j.ic.2003.09.003zbMath1090.68051OpenAlexW2016443407MaRDI QIDQ1887149

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)

Related Items (24)

Parameterized property testing of functions ⋮ Information theory in property testing and monotonicity testing in higher dimension ⋮ On the benefits of adaptivity in property testing of dense graphs ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Improved algorithm for permutation testing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Monotonicity testing and shortest-path routing on the cube ⋮ Algorithmic Aspects of Property Testing in the Dense Graphs Model ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Is submodularity testable? ⋮ Testing of matrix-poset properties ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ Transitive-Closure Spanners: A Survey ⋮ Local Property Reconstruction and Monotonicity ⋮ Unnamed Item ⋮ Tolerant property testing and distance approximation ⋮ Unnamed Item ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Transforming comparison model lower bounds to the parallel-random-access-machine
• Spot-checkers
• Regular Languages are Testable with a Constant Number of Queries
• Property testing and its connection to learning and approximation
• Monotonicity testing over general poset domains
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing monotonicity
• Efficient testing of large graphs
• Property testing in bounded degree graphs

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