Tolerant property testing and distance approximation

DOI10.1016/J.JCSS.2006.03.002MaRDI QIDQ2507697zbMATH OpenOpenAlexFDO

Authors Michal Parnas, Dana Ron, Ronitt Rubinfeld

Publication date 5 October 2006

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2006.03.002

zbMATH Keywords

clusteringapproximationproperty testingsublinear algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Recommendations

• Testing a tolerance hypothesis by means of an information distance
• Distribution-free property testing
• Tolerant versus intolerant testing for Boolean properties
• Publication:4892379
• Property testing and its connection to learning and approximation
• On proximity oblivious testing
• Distribution-Free Property-Testing
• On Proximity-Oblivious Testing
• Approximations induced by tolerance relations

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1756011 (Why is no real title available?)
• scientific article; zbMATH DE number 1857651 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• A sublinear algorithm for weakly approximating edit distance
• Abstract Combinatorial Programs and Efficient Property Testers
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Automata, Languages and Programming
• Better streaming algorithms for clustering problems
• Distribution-free property testing
• Fast approximate PCPs for multidimensional bin-packing problems
• Monotonicity testing over general poset domains
• On the strength of comparisons in property testing
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• STACS 2005
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Testing monotonicity
• Testing of Clustering
• Testing versus estimation of graph properties
• Toward efficient agnostic learning

Cited in

(48)

• Earthmover Resilience and Testing in Ordered Structures
• Introduction to testing graph properties
• Testing versus estimation of graph properties, revisited
• Sublinear-time Algorithms
• Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs
• Erasure-Resilient Property Testing
• scientific article; zbMATH DE number 1875421 (Why is no real title available?)
• Introduction to testing graph properties
• Property-preserving data reconstruction
• The program of the mini-workshop
• Some recent results on local testing of sparse linear codes
• Estimating the longest increasing sequence in polylogarithmic time
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• A unifying theory of distance from calibration
• Tolerant versus intolerant testing for Boolean properties
• Erasures versus errors in local decoding and property testing
• Property testing of the Boolean and binary rank
• Local property reconstruction and monotonicity
• Erasures vs. errors in local decoding and property testing
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Testing Odd-Cycle-Freeness in Boolean Functions
• A brief introduction to property testing
• Testing versus Estimation of Graph Properties
• Tolerant Testers of Image Properties
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• An \(o(n)\) monotonicity tester for Boolean functions over the hypercube
• Brief announcement: Erasure-resilience versus tolerance to errors
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• A Note on Tolerant Testing with One-Sided Error
• The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
• Small space representations for metric min-sum \(k\)-clustering and their applications
• Distributed discovery of large near-cliques
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Approximating the distance to monotonicity of Boolean functions
• Improved algorithm for permutation testing
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Tolerant testers of image properties
• A Brief Introduction to Property Testing
• Robustly self-ordered graphs: constructions and applications to property testing
• Estimating parameters associated with monotone properties
• Local testing of lattices
• Testing \(k\)-monotonicity
• scientific article; zbMATH DE number 6028051 (Why is no real title available?)
• Covert learning: how to learn with an untrusted intermediary
• Additive approximation for edge-deletion problems
• Testing odd-cycle-freeness in Boolean functions
• Sample-based distance-approximation for subsequence-freeness

This page was built for publication: Tolerant property testing and distance approximation

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