Local Correction with Constant Error Rate
A Boolean function f on 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 ? (x)=f ? (x 1,,x n )=f(x ?(1),,x ?(n)) of f, we can compute f ? (x) for any \(x \in\mathbb{Z}_{2}^{n}\) with good probability using q queries to g. It is known that degree d polynomials are O(2 d )-locally correctable, and that most k-juntas are O(klogk)-locally correctable, where the closeness parameter, or more precisely the distance between g and f ? , is required to be exponentially small (in d and k respectively).
local correction juntas partially symmetric functions influence symmetric influence