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

approximationclusteringproperty testingsublinear algorithms

Mathematics Subject Classification ID

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

Recommendations

• Testing a tolerance hypothesis by means of an information distance
• Distribution-free property testing
• Tolerant versus intolerant testing for Boolean properties
• scientific article; zbMATH DE number 927110
• 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

• 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
• 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?)
• 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
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• STACS 2005
• Testing monotonicity
• Testing of Clustering
• Testing versus estimation of graph properties
• Toward efficient agnostic learning

Cited in

(58)

• Additive approximation for edge-deletion problems
• Covert learning: how to learn with an untrusted intermediary
• An o(n) monotonicity tester for Boolean functions over the hypercube
• Tolerant versus intolerant testing for Boolean properties
• A Brief Introduction to Property Testing
• Introduction to testing graph properties
• Testing Odd-Cycle-Freeness in Boolean Functions
• Local testing of lattices
• Tolerant testers of image properties
• Erasure-Resilient Property Testing
• Testing k-monotonicity
• scientific article; zbMATH DE number 1875421 (Why is no real title available?)
• A brief introduction to property testing
• The program of the mini-workshop
• Sublinear-time Algorithms
• Introduction to testing graph properties
• Some recent results on local testing of sparse linear codes
• Local property reconstruction and monotonicity
• Estimating parameters associated with monotone properties
• Brief announcement: Erasure-resilience versus tolerance to errors
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• Erasures vs. errors in local decoding and property testing
• The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
• A Note on Tolerant Testing with One-Sided Error
• Earthmover Resilience and Testing in Ordered Structures
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Testing versus Estimation of Graph Properties
• scientific article; zbMATH DE number 6028051 (Why is no real title available?)
• Estimating the longest increasing sequence in polylogarithmic time
• Testing odd-cycle-freeness in Boolean functions
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Tolerant Testers of Image Properties
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Erasures versus errors in local decoding and property testing
• Approximating the distance to monotonicity of Boolean functions
• Improved algorithm for permutation testing
• A unifying theory of distance from calibration
• Robustly self-ordered graphs: constructions and applications to property testing
• Sample-based distance-approximation for subsequence-freeness
• Distributed discovery of large near-cliques
• Testing versus estimation of graph properties, revisited
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• On the lower bound on the length of relaxed locally decodable codes
• Public coin interactive proofs for label-invariant distribution properties
• Testing intersectingness of uniform families
• Interactive proofs for verifying machine learning
• Erasure-resilient sublinear-time graph algorithms
• Testing intersectingness of uniform families
• New sublinear algorithms and lower bounds for LIS estimation
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier
• Tolerant testers for subgraph-freeness
• Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)
• Property testing of the Boolean and binary rank
• 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

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)