A o(n) monotonicity tester for Boolean functions over the hypercube
Chakrabarty, Deeparnab · Seshadhri, C.
Original · EN
A Boolean function f:{0,1}ⁿ {0,1} is said to be -far from monotone if f needs to be modified in at least -fraction of the points to make it monotone. We design a randomized tester that is given oracle access to f and an input parameter >0, and has the following guarantee: It outputs Yes if the function is monotonically non-decreasing, and outputs No with probability >2/3, if the function is -far from monotone. This non-adaptive, one-sided tester makes O(n⁷/⁸⁻³/²(1/)) queries to the oracle.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.