License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.45
URN: urn:nbn:de:0030-drops-68803
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6880/
Go to the corresponding LIPIcs Volume Portal

Berman, Piotr ; Murzabulatov, Meiram ; Raskhodnikova, Sofya

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

pdf-format:
LIPIcs-FSTTCS-2016-45.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{berman_et_al:LIPIcs:2016:6880,
  author =	{Piotr Berman and Meiram Murzabulatov and Sofya Raskhodnikova},
  title =	{{The Power and Limitations of Uniform Samples in Testing Properties of Figures}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6880},
  URN =		{urn:nbn:de:0030-drops-68803},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.45},
  annote =	{Keywords: Property testing, randomized algorithms, being a half-plane, convexity}
}

Keywords: Property testing, randomized algorithms, being a half-plane, convexity
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI