Local Correction of Juntas

Details Local Correction of Juntas Local Correction of Juntas

2011-09-16

arxiv.org/abs/1109.3639v2

Computer Science

Computational Complexity

6 pages

Scientific paper

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_sigma of f, we can compute f_sigma(x) for any x in Z_2^n 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(2^k)-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(k log k) queries suffice.

Affiliated with

Also associated with

No associations

Rating

Local Correction of Juntas does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Local Correction of Juntas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local Correction of Juntas will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-535210