Abstract
Testing monotonicity of a Boolean function f:{0,1}^n > {0,1} is an important problem in the field of property testing. It has led to connections with many interesting combinatorial questions on the directed hypercube: routing, random walks, and new isoperimetric theorems. Denoting the proximity parameter by epsilon, the best tester is the nonadaptive O~(epsilon^{2}sqrt{n}) tester of KhotMinzerSafra (FOCS 2015). A series of recent results by BelovsBlais (STOC 2016) and ChenWaingartenXie (STOC 2017) have led to Omega~(n^{1/3}) lower bounds for adaptive testers. Reducing this gap is a significant question, that touches on the role of adaptivity in monotonicity testing of Boolean functions.
We approach this question from the perspective of parametrized property testing, a concept recently introduced by PallavoorRaskhodnikovaVarma (ACM TOCT 2017), where one seeks to understand performance of testers with respect to parameters other than just the size. Our result is an adaptive monotonicity tester with onesided error whose query complexity is O(epsilon^{2}I(f)log^5 n), where I(f) is the total influence of the function. Therefore, adaptivity provably helps monotonicity testing for low influence functions.
BibTeX  Entry
@InProceedings{chakrabarty_et_al:LIPIcs:2018:10113,
author = {Deeparnab Chakrabarty and C. Seshadhri},
title = {{Adaptive Boolean Monotonicity Testing in Total Influence Time}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {20:120:7},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770958},
ISSN = {18688969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10113},
URN = {urn:nbn:de:0030drops101133},
doi = {10.4230/LIPIcs.ITCS.2019.20},
annote = {Keywords: Property Testing, Monotonicity Testing, Influence of Boolean Functions}
}
Keywords: 

Property Testing, Monotonicity Testing, Influence of Boolean Functions 
Seminar: 

10th Innovations in Theoretical Computer Science Conference (ITCS 2019) 
Issue Date: 

2018 
Date of publication: 

21.12.2018 