Local correction of juntas
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- A lower bound for testing juntas
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Locally decodable codes
- Nearly tight bounds for testing function isomorphism
- Self-testing/correcting with applications to numerical problems
- Testing Basic Boolean Formulae
- Testing Boolean function isomorphism
- Testing Reed–Muller Codes
- Testing juntas
- Testing juntas nearly optimally
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
This page was built for publication: Local correction of juntas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q437678)
