The power and limitations of uniform samples in testing properties of figures
From MaRDI portal
Publication:666678
DOI10.1007/s00453-018-0467-9zbMath1417.68225OpenAlexW2887874679MaRDI QIDQ666678
Meiram Murzabulatov, Sofya Raskhodnikova, Piotr Berman
Publication date: 11 March 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6880/
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (2) dimensions (including convex curves) (52A10) Randomized algorithms (68W20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Testing periodicity
- Property testing. Current research and surveys
- Another efficient algorithm for convex hulls in two dimensions
- Self-testing/correcting with applications to numerical problems
- Spot-checkers
- Fast-Match: fast affine template matching
- Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
- On Sample-Based Testers
- Testing Convexity of Figures Under the Uniform Distribution
- Property testing and its connection to learning and approximation
- Testing Symmetric Properties of Distributions
- Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
- The complexity of approximating entropy
- Monotonicity testing over general poset domains
- A sublinear algorithm for weakly approximating edit distance
- Partitioning with two lines in the plane
- Testing for Forbidden Order Patterns in an Array
- Tolerant testers of image properties
- The Power and Limitations of Uniform Samples in Testing Properties of Figures
- Parameterized property testing of functions
- Robust Characterizations of Polynomials with Applications to Program Testing
- Testing Properties of Sparse Images
- Optimal unateness testers for real-valued functions: Adaptivity helps
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- lgorithmic and Analysis Techniques in Property Testing
- L p -testing
- Introduction to Property Testing
- Testing Closeness of Discrete Distributions
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Some 3CNF Properties Are Hard to Test
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Testing monotonicity
- Property testing in bounded degree graphs
