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.ITCS.2017.12
URN: urn:nbn:de:0030-drops-81479
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8147/
Go to the corresponding LIPIcs Volume Portal

Pallavoor, Ramesh Krishnan S. ; Raskhodnikova, Sofya ; Varma, Nithin

Parameterized Property Testing of Functions

pdf-format:
LIPIcs-ITCS-2017-12.pdf (0.6 MB)

Abstract

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us to surpass the (worst-case) lower bounds, expressed in terms of the input size, for several problems. Our aim is to develop a similar level of understanding of the complexity of sublinear-time algorithms to the one that was enabled by research in parameterized complexity for classical algorithms.

Specifically, we focus on testing properties of functions. By parameterizing the query complexity in terms of the size r of the image of the input function, we obtain testers for monotonicity and convexity of functions of the form f:[n]\to \mathbb{R} with query complexity O(\log r), with no dependence on n. The result for monotonicity circumvents the \Omega(\log n) lower bound by Fischer (Inf. Comput., 2004) for this problem. We present several other parameterized testers, providing compelling evidence that expressing the query complexity of property testers in terms of the input size is not always the best choice.

BibTeX - Entry

@InProceedings{pallavoor_et_al:LIPIcs:2017:8147,
  author =	{Ramesh Krishnan S. Pallavoor and Sofya Raskhodnikova and Nithin Varma},
  title =	{{Parameterized Property Testing of Functions}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8147},
  URN =		{urn:nbn:de:0030-drops-81479},
  doi =		{10.4230/LIPIcs.ITCS.2017.12},
  annote =	{Keywords: Sublinear algorithms, property testing, parameterization, monotonicity, convexity}
}

Keywords: Sublinear algorithms, property testing, parameterization, monotonicity, convexity
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

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