Local correction of juntas

A Boolean function f over n variables is said to be q-locally correctable if, given a black-box access to a function g   which is “close” to an isomorphism fσfσ of f  , we can compute fσ(x)fσ(x) for any  x∈Z2n with good probability using q queries to g.We observe that any k-junta, that is, any function which depends only on k   of its input variables, is O(k2)O(2k)-locally correctable. Moreover, we show that there are examples where this is essentially best possible, and locally correcting some k-juntas requires a number of queries which is exponential in k. These examples, however, are far from being typical, and indeed we prove that for almost every k  -junta, O(klogk) queries suffice.

► We consider the number of queries needed to locally correct k-juntas. ► For every input x  , we must recover f(x)f(x) with good probability using few queries to f. ► We observe that for every k  -junta, O(k2)O(2k) queries suffice for local correction. ► This is best possible as we show some k-juntas require exponential number of queries. ► However, for most k  -juntas we provide an algorithm which performs O(klogk) queries.