On the strength of comparisons in property testing

DOI10.1016/J.IC.2003.09.003zbMATH Open1090.68051OpenAlexW2016443407MaRDI QIDQ1887149FDOQ1887149

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

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

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)

Cites Work

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

Cited In (31)

• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Title not available (Why is that?)
• 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
• Transitive-closure spanners: a survey
• Local property reconstruction and monotonicity
• Monotonicity testing and shortest-path routing on the cube
• On the benefits of adaptivity in property testing of dense graphs
• Improved bounds for testing forbidden order patterns
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Information theory in property testing and monotonicity testing in higher dimension
• 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
• Property testing of massively parametrized problems -- a survey

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)