Tolerant property testing and distance approximation

DOI10.1016/j.jcss.2006.03.002zbMath1100.68109MaRDI QIDQ2507697

Dana Ron, Michal Parnas, 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

clustering; approximation; property testing; sublinear algorithms

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68W25: Approximation algorithms

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, The Program of the Mini-Workshop, Sublinear-time Algorithms, Some Recent Results on Local Testing of Sparse Linear Codes, Local Property Reconstruction and Monotonicity, Distributed discovery of large near-cliques, Property-preserving data reconstruction, Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs, Small space representations for metric min-sum \(k\)-clustering and their applications, Additive approximation for edge-deletion problems, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Self-testing/correcting with applications to numerical problems
• Toward efficient agnostic learning
• Spot-checkers
• Fast approximate PCPs for multidimensional bin-packing problems
• On the strength of comparisons in property testing
• Property testing and its connection to learning and approximation
• Monotonicity testing over general poset domains
• A sublinear algorithm for weakly approximating edit distance
• Better streaming algorithms for clustering problems
• Testing versus estimation of graph properties
• Testing of Clustering
• Robust Characterizations of Polynomials with Applications to Program Testing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Abstract Combinatorial Programs and Efficient Property Testers
• Automata, Languages and Programming
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• STACS 2005
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing monotonicity