A o(n) Monotonicity Tester for Boolean Functions on the Hypercube

Deeparnab Chakrabarty; C. Seshadhri

A o(n) Monotonicity Tester for Boolean Functions on the Hypercube

Deeparnab Chakrabarty ,
C. Seshadhri

STOC '13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing, Palo Alto, California, USA | June 2013

Published by ACM New York, NY, USA

Publication

Download BibTex

Given oracle access to a Boolean function f:01n01 , we design a randomized tester that takes as input a parameter \eps0, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability 23 , if the function is \eps-far from monotone. That is, f needs to be modified at \eps-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes O(n78\eps−32) queries to the oracle.