A o(n) monotonicity tester for boolean functions over the hypercube

Given oracle access to a Boolean function f:{0,1} n -> {0,1}, we design a randomized tester that takes as input a parameter ε>0, and outputs Yes if the function is monotonically non-increasing, and outputs No with probability >2/3, if the function is ε-far from being monotone, that is, f needs to be modified at ε-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes ~O(n 5/6 ε -5/3 ) queries to the oracle.

Authors

• Deeparnab Chakrabarty
• C. Seshadhri 0001

Keywords

• boolean functions
• boolean hypercube
• monotonicity
• property testing