Abstract
This paper investigates the feasibility of local correction for Boolean functions—specifically juntas and partially symmetric functions—under a constant noise rate. We demonstrate that for "almost every" function in these classes, it is possible to recover the true value at any point using $O(k \log^2 k)$ non-adaptive queries, even when the input variables are permuted and the function is corrupted by constant noise.
Introduction
Local correction involves computing the value of a function $f$ at a specific point $x$ by querying a noisy version $g$ at a small number of other points. Traditionally, such algorithms required the noise rate $\epsilon$ to be negligible. This research addresses whether local correction can be performed when $\epsilon$ is a constant, independent of the input dimension $n$. We focus on $k$-juntas, which depend on only $k$ variables, and partially symmetric functions.
Methodology: Testing-by-Implicit-Learning
The proposed correction framework for juntas operates in two primary phases. First, the algorithm must identify which variables are influential. Since $n$ can be very large, the algorithm partitions variables into sets and identifies those containing influential variables.
As shown in Algorithm 2, the FIND-INFLUENCING-SETS procedure uses a randomized approach to isolate sets $I_i$ that contribute significantly to the function's output. Following identification, the algorithm recovers the internal permutation of these variables by maximizing agreement between sampled noisy values and the known function core. For partially symmetric functions, the authors utilize "symmetric influence" to distinguish asymmetric "anchor" variables from the symmetric background.
Key Results and Theoretical Bounds
The study provides both upper and lower bounds for local correction:
- Juntas and Symmetric Functions: Almost every $k$-junta or $(n-k)$-symmetric function can be corrected from a constant noise rate (e.g., $\epsilon = 0.001$) using $O(k \log^2 k)$ queries.
- The "Almost Every" Property: The authors prove that correction is impossible for all juntas, as some functions have influences too small to be distinguished from noise.
- General Hardness: For arbitrary Boolean functions, local correction is shown to be hard, requiring $\Omega(n)$ queries even for minimal noise.
Discussion and Future Work
While this work establishes the possibility of local correction under constant noise for specific classes, several questions remain. The current noise threshold $\epsilon$ is relatively small, and the extension to other structured classes like low-degree polynomials is an open problem. Additionally, characterizing the specific structural properties that allow a non-random function to be corrected remains a significant challenge for future research.
Summary updated