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

Baleshzar, Roksana ; Chakrabarty, Deeparnab ; Pallavoor, Ramesh Krishnan S. ; Raskhodnikova, Sofya ; Seshadhri, C.

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

pdf-format:
LIPIcs-ICALP-2017-5.pdf (0.6 MB)

Abstract

We study the problem of testing unateness of functions f:{0,1}^d -> R. We give an O(d/\epsilon . log(d/\epsilon))-query nonadaptive tester and an O(d/\epsilon)-query adaptive tester and show that both testers are optimal for a fixed distance parameter \epsilon. Previously known unateness testers worked only for Boolean functions, and their query complexity had worse dependence on the dimension both for the adaptive and the nonadaptive case. Moreover, no lower bounds for testing unateness were known. We generalize our results to obtain optimal unateness testers for functions f:[n]^d -> R.

Our results establish that adaptivity helps with testing unateness of real-valued functions on domains of the form {0,1}^d and, more generally, [n]^d. This stands in contrast to the situation for monotonicity testing where there is no adaptivity gap for functions f:[n]^d -> R.

BibTeX - Entry

@InProceedings{baleshzar_et_al:LIPIcs:2017:7484,
  author =	{Roksana Baleshzar and Deeparnab Chakrabarty and Ramesh Krishnan S. Pallavoor and Sofya Raskhodnikova and C. Seshadhri},
  title =	{{Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7484},
  URN =		{urn:nbn:de:0030-drops-74844},
  doi =		{10.4230/LIPIcs.ICALP.2017.5},
  annote =	{Keywords: Property testing, unate and monotone functions}
}

Keywords: Property testing, unate and monotone functions
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

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