Local correction of juntas

Noga Alon, Amit Weinstein

Research output: Contribution to journalArticle

3 Scopus citations

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 of f, we can compute (x) for any xZ2n 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(klogk) queries suffice.

Original languageEnglish (US)
Pages (from-to)223-226
Number of pages4
JournalInformation Processing Letters
Volume112
Issue number6
DOIs
StatePublished - Mar 15 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Local correction
  • Locally correctable codes
  • Randomized algorithms

Fingerprint Dive into the research topics of 'Local correction of juntas'. Together they form a unique fingerprint.

  • Cite this