Local Correction with Constant Error Rate

Noga Alon, Amit Weinstein

Research output: Contribution to journalArticle

Abstract

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σ(x1,…,xn)=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(2d)-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). In this work we relax the requirement for the closeness parameter by allowing the distance between the functions to be a constant. We first investigate the family of juntas, and show that almost every k-junta is O(klog2k)-locally correctable for any distance ε<0.001. A similar result is shown for the family of partially symmetric functions, that is functions which are indifferent to any reordering of all but a constant number of their variables. For both families, the algorithms provided here use non-adaptive queries and are applicable to most but not all functions of each family (as it is shown to be impossible to locally correct all of them). Our approach utilizes the measure of symmetric influence introduced in the recent analysis of testing partial symmetry of functions.

Original languageEnglish (US)
Pages (from-to)496-516
Number of pages21
JournalAlgorithmica
Volume71
Issue number2
DOIs
StatePublished - Feb 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Influence
  • Juntas
  • Local correction
  • Partially symmetric functions
  • Symmetric influence

Fingerprint Dive into the research topics of 'Local Correction with Constant Error Rate'. Together they form a unique fingerprint.

  • Cite this