Tolerant property testing and distance approximation
From MaRDI portal
Publication:2507697
DOI10.1016/J.JCSS.2006.03.002zbMATH Open1100.68109OpenAlexW2073966617MaRDI QIDQ2507697FDOQ2507697
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
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
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)
Cites Work
- Property testing and its connection to learning and approximation
- Self-testing/correcting with applications to numerical problems
- Spot-checkers
- Fast approximate PCPs for multidimensional bin-packing problems
- Monotonicity testing over general poset domains
- Robust Characterizations of Polynomials with Applications to Program Testing
- Title not available (Why is that?)
- Testing monotonicity
- Toward efficient agnostic learning
- Title not available (Why is that?)
- Title not available (Why is that?)
- Abstract Combinatorial Programs and Efficient Property Testers
- On the strength of comparisons in property testing
- A sublinear algorithm for weakly approximating edit distance
- Distribution-free property testing
- Testing versus estimation of graph properties
- Better streaming algorithms for clustering problems
- Testing of Clustering
- Automata, Languages and Programming
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Title not available (Why is that?)
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- STACS 2005
Cited In (47)
- Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs
- Property testing of the Boolean and binary rank
- Improved algorithm for permutation testing
- Sublinear-time Algorithms
- Erasure-Resilient Property Testing
- Title not available (Why is that?)
- 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
- Property-preserving data reconstruction
- Tolerant versus intolerant testing for Boolean properties
- Estimating parameters associated with monotone properties
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Local testing of lattices
- Testing \(k\)-monotonicity
- Sample-based distance-approximation for subsequence-freeness
- The program of the mini-workshop
- Some recent results on local testing of sparse linear codes
- An \(o(n)\) monotonicity tester for Boolean functions over the hypercube
- Earthmover Resilience and Testing in Ordered Structures
- Erasures versus errors in local decoding and property testing
- A Brief Introduction to Property Testing
- Testing odd-cycle-freeness in Boolean functions
- Local property reconstruction and monotonicity
- A brief introduction to property testing
- Additive approximation for edge-deletion problems
- Introduction to testing graph properties
- Testing versus estimation of graph properties, revisited
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Introduction to testing graph properties
- Erasures vs. errors in local decoding and property testing
- Approximating the distance to monotonicity of Boolean functions
- Testing versus Estimation of Graph Properties
- Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
- Title not available (Why is that?)
- Estimating the longest increasing sequence in polylogarithmic time
- Tolerant testers of image properties
- A unifying theory of distance from calibration
- Topics and Techniques in Distribution Testing: A Biased but Representative Sample
- Brief announcement: Erasure-resilience versus tolerance to errors
- Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
- Covert learning: how to learn with an untrusted intermediary
- Title not available (Why is that?)
- Flipping out with many flips: hardness of testing \(k\)-monotonicity
- Distributed discovery of large near-cliques
- Testing Odd-Cycle-Freeness in Boolean Functions
- Robustly self-ordered graphs: constructions and applications to property testing
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)
