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.APPROX-RANDOM.2018.31
URN: urn:nbn:de:0030-drops-94350
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9435/
Go to the corresponding LIPIcs Volume Portal

Belovs, Aleksandrs

Adaptive Lower Bound for Testing Monotonicity on the Line

pdf-format:
LIPIcs-APPROX-RANDOM-2018-31.pdf (0.4 MB)

Abstract

In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the objects are functions from one poset to another. This is an active area of research. In this paper we study query complexity of epsilon-testing monotonicity of a function f : [n]->[r]. All our lower bounds are for adaptive two-sided testers.
- We prove a nearly tight lower bound for this problem in terms of r. The bound is Omega((log r)/(log log r)) when epsilon = 1/2. No previous satisfactory lower bound in terms of r was known.
- We completely characterise query complexity of this problem in terms of n for smaller values of epsilon. The complexity is Theta(epsilon^{-1} log (epsilon n)). Apart from giving the lower bound, this improves on the best known upper bound.
Finally, we give an alternative proof of the Omega(epsilon^{-1}d log n - epsilon^{-1}log epsilon^{-1}) lower bound for testing monotonicity on the hypergrid [n]^d due to Chakrabarty and Seshadhri (RANDOM'13).

BibTeX - Entry

@InProceedings{belovs:LIPIcs:2018:9435,
  author =	{Aleksandrs Belovs},
  title =	{{Adaptive Lower Bound for Testing Monotonicity on the Line}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{31:1--31:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9435},
  URN =		{urn:nbn:de:0030-drops-94350},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.31},
  annote =	{Keywords: property testing, monotonicity on the line, monotonicity on the hypergrid}
}

Keywords: property testing, monotonicity on the line, monotonicity on the hypergrid
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

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