Tolerant property testing and distance approximation
From MaRDI portal
Publication:2507697
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
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, 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
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