Tolerant property testing and distance approximation

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

Ronitt Rubinfeld, Michal Parnas, Dana Ron

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)

Related Items

Property testing of the Boolean and binary rank, Testing Odd-Cycle-Freeness in Boolean Functions, Additive approximation for edge-deletion problems, Local Testing of Lattices, The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution, A Note on Tolerant Testing with One-Sided Error, Erasures versus errors in local decoding and property testing, Approximating the distance to monotonicity of Boolean functions, Improved algorithm for permutation testing, Unnamed Item, Unnamed Item, Erasure-Resilient Property Testing, Covert learning: how to learn with an untrusted intermediary, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, Property-preserving data reconstruction, Distributed discovery of large near-cliques, Almost Optimal Distribution-Free Sample-Based Testing of k-Modality, Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs, Estimating the Longest Increasing Sequence in Polylogarithmic Time, Small space representations for metric min-sum \(k\)-clustering and their applications, The Program of the Mini-Workshop, Sublinear-time Algorithms, Some Recent Results on Local Testing of Sparse Linear Codes, Local Property Reconstruction and Monotonicity, Unnamed Item, Unnamed Item, Earthmover Resilience and Testing in Ordered Structures, An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, Estimating parameters associated with monotone properties, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, Unnamed Item, Unnamed Item, Topics and Techniques in Distribution Testing: A Biased but Representative Sample

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