Document Open Access Logo

The Power and Limitations of Uniform Samples in Testing Properties of Figures

Authors Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.45.pdf
  • Filesize: 1.83 MB
  • 14 pages

Document Identifiers

Author Details

Piotr Berman
Meiram Murzabulatov
Sofya Raskhodnikova

Cite AsGet BibTex

Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. The Power and Limitations of Uniform Samples in Testing Properties of Figures. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FSTTCS.2016.45

Abstract

We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter epsilon in (0,1/2), a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it does not. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(1/epsilon) samples. In contrast, we prove that convexity can be tested with O(1/epsilon) queries by testers that can make queries of their choice while uniform testers for this property require Omega(1/epsilon^{5/4}) samples. Previously, the fastest known tester for convexity needed Theta(1/epsilon^{4/3}) queries.
Keywords
  • Property testing
  • randomized algorithms
  • being a half-plane
  • convexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of the testable graph properties: It’s all about regularity. SIAM J. Comput., 39(1):143-167, 2009. Google Scholar
  2. A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Inf. Process. Lett., 9(5):216-219, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90072-3.
  3. Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing closeness of discrete distributions. J. ACM, 60(1):4, 2013. Google Scholar
  4. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Testing convexity of figures under the uniform distribution. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, volume 51 of LIPIcs, pages 17:1-17:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.17.
  5. Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. Tolerant Testers of Image Properties. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 90:1-90:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.90.
  6. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 164-173, 2014. URL: http://dx.doi.org/10.1145/2591796.2591887.
  7. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. Google Scholar
  8. Artur Czumaj and Christian Sohler. Property testing with geometric queries. In Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings, pages 266-277, 2001. Google Scholar
  9. Artur Czumaj, Christian Sohler, and Martin Ziegler. Property testing in computational geometry. In Algorithms - ESA 2000, 8th Annual European Symposium, Saarbrücken, Germany, September 5-8, 2000, Proceedings, pages 155-166, 2000. Google Scholar
  10. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM'99, Berkeley, CA, USA, pages 97-108, 1999. Google Scholar
  11. Herbert Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer, 1987. Google Scholar
  12. O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. Google Scholar
  13. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Combinatorica, 20(3):301-337, 2000. Google Scholar
  14. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: http://dx.doi.org/10.1145/285055.285060.
  15. Oded Goldreich and Dana Ron. On sample-based testers. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 337-345, 2015. Google Scholar
  16. Igor Kleiner, Daniel Keren, Ilan Newman, and Oren Ben-Zwi. Applying property testing to an image partitioning problem. IEEE Trans. Pattern Anal. Mach. Intell., 33(2):256-265, 2011. URL: http://dx.doi.org/10.1109/TPAMI.2010.165.
  17. Simon Korman, Daniel Reichman, and Gilad Tsur. Tight approximation of image matching. CoRR, abs/1111.1713, 2011. Google Scholar
  18. Simon Korman, Daniel Reichman, Gilad Tsur, and Shai Avidan. Fast-match: Fast affine template matching. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, June 23-28, 2013, pages 2331-2338, 2013. URL: http://dx.doi.org/10.1109/CVPR.2013.302.
  19. Nimrod Megiddo. Partitioning with two lines in the plane. J. Algorithms, 6(3):430-433, 1985. Google Scholar
  20. Luis Rademacher and Santosh Vempala. Testing geometric convexity. In FSTTCS, pages 469-480, 2004. Google Scholar
  21. Sofya Raskhodnikova. Approximate testing of visual properties. In RANDOM-APPROX, pages 370-381, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45198-3_31.
  22. Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM J. Comput., 39(3):813-842, 2009. Google Scholar
  23. Dana Ron and Gilad Tsur. Testing properties of sparse images. ACM Trans. Algorithms, 10(4):17:1-17:52, 2014. Google Scholar
  24. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. Google Scholar
  25. Bernd Schmeltz. Learning convex sets under uniform distribution. In Data Structures and Efficient Algorithms, Final Report on the DFG Special Joint Initiative, pages 204-213, 1992. Google Scholar
  26. Wojciech Szpankowski. Average Case Analysis of Algorithms on Sequences. John Wiley &Sons, Inc., New York, 2001. Google Scholar
  27. John W. Tukey. Mathematics and the picturing of data. In Proceedings of the international congress of mathematicians, volume 2, pages 523-531, 1975. Google Scholar
  28. Paul Valiant. Testing symmetric properties of distributions. SIAM J. Comput., 40(6):1927-1968, 2011. URL: http://dx.doi.org/10.1137/080734066.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact