# Local Correction of Linear Functions over the Boolean Cube

Prashanth Amireddy School of Engineering and Applied Sciences, Harvard
University, Cambridge, Massachusetts, USA. Supported in part by a Simons
Investigator Award and NSF Award CCF 2152413 to Madhu Sudan and a Simons
Investigator Award to Salil Vadhan. Email<EMAIL_ADDRESS>Amik Raj
Behera Department of Computer Science, Aarhus University, Aarhus, Denmark.
Supported by Srikanth Srinivasan’s start-up grant from Aarhus University.
Email<EMAIL_ADDRESS>Manaswi Paraashar Department of Computer Science,
University of Copenhagen, Denmark. Supported by Srikanth Srinivasan’s start-up
grants from Aarhus University and the University of Copenhagen. Email:
<EMAIL_ADDRESS>Srikanth Srinivasan Department of Computer Science,
University of Copenhagen, Denmark. Also partially employed by Aarhus
University, Denmark. This work was supported by start-up grants from Aarhus
University and the University of Copenhagen. Email<EMAIL_ADDRESS>Madhu Sudan
School of Engineering and Applied Sciences, Harvard University, Cambridge,
Massachusetts, USA. Supported in part by a Simons Investigator Award and NSF
Award CCF 2152413. Email<EMAIL_ADDRESS>
###### Abstract

We consider the task of locally correcting, and locally list-correcting,
multivariate linear functions over the domain $\\{0,1\\}^{n}$ over arbitrary
fields and more generally Abelian groups. Such functions form error-correcting
codes of relative distance $1/2$ and we give local-correction algorithms
correcting up to nearly $1/4$-fraction errors making
$\widetilde{\mathcal{O}}(\log n)$ queries. This query complexity is optimal up
to $\mathop{\mathrm{poly}}(\log\log n)$ factors. We also give local list-
correcting algorithms correcting $(1/2-\varepsilon)$-fraction errors with
$\widetilde{\mathcal{O}}_{\varepsilon}(\log n)$ queries.

These results may be viewed as natural generalizations of the classical work
of Goldreich and Levin whose work addresses the special case where the
underlying group is $\mathbb{Z}_{2}$. By extending to the case where the
underlying group is, say, the reals, we give the first non-trivial locally
correctable codes (LCCs) over the reals (with query complexity being sublinear
in the dimension (also known as message length)).

Previous works in the area mostly focused on the case where the domain is a
vector space or a group and this lends to tools that exploit symmetry. Since
our domains lack such symmetries, we encounter new challenges whose resolution
may be of independent interest. The central challenge in constructing the
local corrector is constructing “nearly balanced vectors” over
$\\{-1,1\\}^{n}$ that span $1^{n}$ — we show how to construct
$\mathcal{O}(\log n)$ vectors that do so, with entries in each vector summing
to $\pm 1$. The challenge to the local-list-correction algorithms, given the
local corrector, is principally combinatorial, i.e., in proving that the
number of linear functions within any Hamming ball of radius
$(1/2-\varepsilon)$ is $\mathcal{O}_{\varepsilon}(1)$. Getting this general
result covering every Abelian group requires integrating a variety of known
methods with some new combinatorial ingredients analyzing the structural
properties of codewords that lie within small Hamming balls.

###### Contents

  1. 1 Introduction
    1. 1.1 Motivation for Our Work
    2. 1.2 Our Main Results
    3. 1.3 Proof Overview
      1. 1.3.1 Local Correction - Theorem 1.1
      2. 1.3.2 Combinatorial List Decoding Bound - Theorem 1.2
      3. 1.3.3 Local List Correction - Theorem 1.3
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Basic Definitions and Tools
  3. 3 Local Correction in the Unique Decoding Regime
    1. 3.1 Sub-Constant Error
      1. 3.1.1 Framework of Local Correction Algorithm
      2. 3.1.2 Local Correction Algorithm for Linear Polynomials
      3. 3.1.3 Correction Gadget for all 1s Vector
    2. 3.2 Constant Error Algorithm via Error-Reduction
      1. 3.2.1 The Base Algorithm and its Analysis
    3. 3.3 Error Close to Half the Minimum Distance (Proof of Theorem 1.1)
  4. 4 Combinatorial Bound for List Decoding Linear Polynomials
    1. 4.1 Combinatorial Bound for Product of $p$-groups ($p\geq 5$)
      1. 4.1.1 Sparsity and Anti-concentration
      2. 4.1.2 Union of Supports is Small
      3. 4.1.3 Union of Supports is Large
    2. 4.2 Combinatorial Bound for $2$ and $3$-groups
      1. 4.2.1 Proof of Lemma 4.15 (Extended Johnson Bound)
      2. 4.2.2 Proof of Combinatorial Bound for a Product of $2$ and $3$-groups
  5. 5 Local List Correction Algorithm
    1. 5.1 Overview of the Algorithms
    2. 5.2 The Algorithms
    3. 5.3 Analysis of the Algorithms
  6. A Non-Local Algorithms for Decoding Low-Degree Polynomials
    1. A.1 Proof Sketch of Theorem A.1
    2. A.2 Proof Sketch of Theorem A.2
  7. B Improved Local Correction over Reals

##  1 Introduction

In this paper we consider the class of “linear” functions mapping
$\\{0,1\\}^{n}$ to an Abelian group and give “local correction” and “local
list-correction” algorithms for this family (of codes). We describe our
problems and results in detail below. We start with some basic notation.

We denote the space of functions mapping $\\{0,1\\}^{n}$ to an Abelian group
$G$ by $\mathcal{F}(\\{0,1\\}^{n},G)$. Given two functions $f,g$ from this
set, we denote by $\delta(f,g)$ the fractional Hamming distance between them,
i.e. the fraction of points in $\\{0,1\\}^{n}$ on which $f$ and $g$ disagree.
In other words,

$\delta(f,g)=\mathop{\mathrm{Pr}}_{x\sim\\{0,1\\}^{n}}[f(x)\neq g(x)].$

We say that $f,g$ are $\delta$-close if $\delta(f,g)\leq\delta$ and that $f,g$
are $\delta$-far otherwise. Given a set of functions
$\mathcal{F}\subseteq\mathcal{F}(\\{0,1\\}^{n},G)$, we denote by
$\delta(f,\mathcal{F})$ the minimum distance between $f$ and a function
$P\in\mathcal{F}.$ The function $f$ is said to be $\delta$-close if
$\delta(f,\mathcal{F})\leq\delta$ and otherwise $\delta$-far from
$\mathcal{F}.$ We denote by $\delta(\mathcal{F})$ the minimum distance between
two distinct functions in $\mathcal{F}.$

The main thrust of this paper is getting efficient local correcting algorithms
for some basic classes of functions $\mathcal{F}$ that correct close to
$\delta(\mathcal{F})/2$ fraction of errors uniquely (i.e. given
$f:\\{0,1\\}^{n}\to G$ determine $P\in\mathcal{F}$ such that
$\delta(f,P)<\delta(\mathcal{F})/2$), and to list-correct close to
$\delta(\mathcal{F})$ fraction of errors with small sized lists (i.e., given
$f$ output a small list $P_{1},\ldots,P_{L}\in\mathcal{F}$ containing all
functions $P$ such that $\delta(f,P)<\delta(\mathcal{F})-\varepsilon$). We
start by describing our class of functions.

##### Group valued polynomials.

The function spaces we are interested in are defined by polynomials of low-
degree over the Boolean cube $\\{0,1\\}^{n}$ with coefficients from an Abelian
group $G$, where we view $\\{0,1\\}\subseteq\mathbb{Z}$. (Thus a monomial
function is given by a group element $g\in G$ and subset $S\subseteq[n]$ and
takes the value $g$ at points $a\in\\{0,1\\}^{n}$ such that $a_{i}=1$ for all
$i\in S$. The degree of a monomial is $|S|$ and a degree $d$ polynomial is the
sum of monomials of degree at most $d$.) We let
$\mathcal{P}_{d}(\\{0,1\\}^{n},G)$ denote the space of polynomials of degree
at most $d$ in this setting. (If $n$ and $G$ are clear from context we refer
to this class as simply $\mathcal{P}_{d}$.) The standard proof of the
“Schwartz-Zippel Lemma” (dating back at least to Ore [Ore22]) extends to this
setting (see Theorem 2.1) and shows that two distinct degree $d$ polynomials
differ on at least a $2^{-d}$ fraction of $\\{0,1\\}^{n}$. Therefore
$\delta(\mathcal{P}_{d})=2^{-d}$ and our goal is to correct half this fraction
of errors uniquely and close to this fraction of errors with small-sized
lists. (We do so for $d=1$, though many results apply to general values of
$d$.) Next, we describe our notion of efficiency for correction.

##### Local Correction.

In this work we are interested in a particularly strong notion of decoding,
namely “local correction”. Informally, $\mathcal{F}$ is locally correctable if
there exists a probabilistic algorithm $C$ that, given a point
$\mathbf{x}\in\\{0,1\\}^{n}$ and oracle access to a function $f$ that is close
to $\mathcal{F}$, computes $P(\mathbf{x})$ with high probability while making
few queries to the oracle $f$, where $P$ is function in $\mathcal{F}$ closest
to $f$. In contrast to the usual notion of decoding which would require
explicitly outputting a description of $P$ (say the coefficients of $P$ when
$\mathcal{F}=\mathcal{P}_{d}$) this notion thus only requires us to compute
$P(\mathbf{x})$ for a given $\mathbf{x}$. The main parameters associated with
a local correction algorithm are the fraction of errors it corrects and the
number of queries it makes to the oracle $f$. Formally, we say $\mathcal{F}$
is $(\delta,q)$-locally correctable if there exists a probabilistic algorithm
that given $\mathbf{a}\in\\{0,1\\}^{n}$ and oracle access to the input
polynomial $f$ that is $\delta$-close to $P\in\mathcal{F}$, outputs
$P(\mathbf{a})$ correctly with probability at least $3/4$ by making at most
$q$ queries to $f$.

The question of local correction of low-degree polynomials has been widely
studied [BF90, GLR+91, GS92, STV01]. These works have focused on the setting
when the domain has an algebraic structure such as being a vector space over a
finite field. In contrast the “Schwartz-Zippel” lemma only requires the domain
to be a product space. Kim and Kopparty [KK17] were the first to study the
decoding of low-degree multivariate polynomials when the domain is a product
set, though they do not study local correctibility. Bafna, Srinivasan, and
Sudan [BSS20] were the first to study the problem of local correctibility of
linear polynomials, though their result was mainly a negative result. They
showed that if the underlying field $\mathbb{F}$ is large, for example,
$\mathbb{F}=\mathbb{R}$, then any $(\Omega(1),q)$-local correction algorithm
for $\mathcal{P}_{1}$ with constant $\delta$ requires at least
$\tilde{\Omega}(\log n)$ queries. In this work, we consider the task of
designing local correction algorithms with nearly matching performance.

##### Local List Correction.

When considering a fraction of errors larger than $\delta(\mathcal{F})/2$, the
notion of correction that one usually appeals to is called “list-decoding” or
“list-correction” as we will refer to it, to maintain a consistent distinction
between the notion of recovering the message (decoding) and recovering its
encoding (correction). Here the problem comes in two phases: First a
combinatorial challenge of proving that for some parameter
$\rho\in[\delta(\mathcal{F})/2,\delta(\mathcal{F})]$ we have an a priori bound
$L=L(\rho)$ such that for every function $f:\\{0,1\\}^{n}\to G$ there are at
most $t\leq L$ functions $P_{1},\ldots,P_{t}\in\mathcal{F}$ satisfying
$\delta(f,P_{i})\leq\rho$. We define $\mathcal{F}$ to be $(\rho,L)$-list-
decodable if it satisfies this property. Next comes the algorithmic challenge
of finding the list of size of most $L$ that includes all such $P_{i}$’s. In
the non-local setting, this is referred to as the list correction task. In the
local setting, the task is subtler to define and was formalized by Sudan,
Trevisan, and Vadhan [STV01] as follows:
A $(\rho,L,q)$-local-list-corrector for $\mathcal{F}$ is a probabilistic
algorithm $C$ that takes as input an index $i\in[L]$ and
$\mathbf{x}\in\\{0,1\\}^{n}$ along with oracle access to $f:\\{0,1\\}^{n}\to
G$ such that $C^{f}(i,\mathbf{x})$ is computed with at most $q$ oracle calls
to $f$ and $C$ satisfies the following property: For every polynomial
$P\in\mathcal{F}$ such that $\delta(f,P)\leq\rho$ there exists an index
$i\in[L]$ such that for every $\mathbf{x}\in\\{0,1\\}^{n}$,
$\Pr[C^{f}(i,\mathbf{x})=P(\mathbf{x})]\geq 3/4$. (In other words
$C^{f}(i,\cdot)$ provides oracle access to $P$ and ranging over $i\in[L]$
gives oracle access to every $P_{1},\ldots,P_{t}$ that are $\rho$-close to
$f$, while some $i$ may output spurious functions.)

The notion of list-decoding dates back to the work of Elias [Eli57]. The
seminal work of Goldreich and Levin [GL89] produced the first non-trivial
list-decoders for any non-trivial class of functions. (Their work happens to
consider the class $\mathcal{F}=\mathcal{P}_{1}(\\{0,1\\}^{n},\mathbb{Z}_{2})$
and actually give local list-decoders, though not strictly local list-
correctors.) List-decoding of Reed-Solomon codes was studied by Sudan [Sud97]
and Guruswami and Sudan [GS99]. Local list-correction algorithms for functions
mapping $\mathbb{F}_{q}^{n}$ to $\mathbb{F}_{q}$ for polynomials of degree
$d\ll q$ were given in [STV01]. The setting of $d>q$ has been considered by
Gopalan, Klivans and Zuckerman [GKZ08] and Bhowmick and Lovett [BL18]. In a
somewhat different direction Dinur, Grigorescu, Kopparty, and Sudan [GKS06,
DGKS08] consider the class of homomorphisms from $G$ to $H$ for finite Abelian
groups $G$ and $H$, and give local list-correction algorithms for such classes
of functions.

In this work, we give local list-correction algorithms for the class
$\mathcal{P}_{1}(\\{0,1\\}^{n},G)$ for every Abelian group $G$. We explain the
significance of this work in the broader context below.

###  1.1 Motivation for Our Work

The problem of decoding linear polynomials over $\\{0,1\\}^{n}$ over an
arbitrary Abelian group is a natural generalization of the work of Goldreich
and Levin, who consider this problem over $\mathbb{Z}_{2}$. However, the
error-correcting properties of the underlying code (rate and distance) remain
the same over any Abelian group $G$. Further, standard non-local algorithms
[Ree54] over $\mathbb{Z}_{2}$ work almost without change over any $G$ (see
Appendix A). The local correction problem is, therefore, a natural next step.

There are also other technical motivations for our work from the limitations
of known techniques. Perhaps the clearest way to highlight these limitations
is that to date we have no $(\Omega(1),O(1))$-locally correctable codes over
the reals with growing dimension. This glaring omission is highlighted in the
results of [BDYW11, DSW14, DSW17]. The work of Barak, Dvir, Wigderson and
Yehudayoff [BDYW11] and the followup of Dvir, Saraf, and Wigderson [DSW14]
show that there are no $(\Omega(1),2)$-locally correctable codes of super-
constant dimension, while another result of Dvir, Saraf and Wigderson [DSW17]
shows that any $(\Omega(1),3)$-locally correctable codes in $\mathbb{R}^{n}$
must have dimension at most $n^{1/2-\Omega(1)}.$ Indeed, till our work, there
has been very little exploration of code constructions over the reals. While
our work does not give an $(\Omega(1),O(1))$-locally correctable code either,
ours is the first to give $n$-dimensional codes that are
$(\Omega(1),\widetilde{O}(\log n))$-locally correctable. (These are obtained
by setting $G=\mathbb{R}$ in our results.)

A technical reason why existing local correction results do not cover any
codes over the reals is that almost all such results rely on the underlying
symmetries of the domain. Typical results in the area (including all the
results cited above) work over a domain that is either a vector space or at
least a group. Automorphisms of the domain effectively play a central role in
the design and analysis of the local correction algorithms; but they also
force the range of the function to be related to the domain and this restricts
their scope. In our setting, while the domain $\\{0,1\\}^{n}$ does have some
symmetries, they are much less rich and unrelated to the structure of the
range. Thus new techniques are needed to design and analyze local-correction
algorithms in this setting. Indeed we identify a concrete new challenge — the
design of “balanced” vectors in $\\{-1,1\\}^{n}$ (i.e., with sum of entries
being in $\\{-1,1\\}$) that span the vector $1^{n}$ — that enables local
correction, and address this challenge. We remark that correcting
$\mathcal{P}_{d}$ for $d>1$ leads to even more interesting challenges that
remain open.

A final motivation is just the combinatorics of the list-decodability of this
space. For instance for the class
$\mathcal{F}=\mathcal{P}_{1}(\\{0,1\\}^{n},G)$ for any $G$, it is
straightforward to show $\delta(\mathcal{F})=1/2$ and so the unique decoding
radius is $1/4$, but the list-decoding radius was not understood prior to this
work. The general bound in this setting would be the Johnson bound which only
promises a list-decoding radius of $1-1/\sqrt{2}\approx 0.29$. Indeed a
substantial portion of this work is to establish that the list-decoding radius
of all these codes approaches $\delta(\mathcal{F})=1/2$.

We describe our results below before turning to the proof techniques.

###  1.2 Our Main Results

Our first result is an almost optimal local correction algorithm for degree 1
polynomials up to an error slightly less than $1/4$, which is the unique
decoding radius.

######  Theorem 1.1 (Local correction algorithms for $\mathcal{P}_{1}$ up to
the unique decoding radius).

The space $\mathcal{P}_{1}$ has a $(\delta,q)$-local correction algorithm
where $\delta=\frac{1}{4}-\varepsilon$ for any constant $\varepsilon>0$ and
$q=\tilde{O}(\log n).$

We remark that Theorem 1.1 is tight up to $\mathop{\mathrm{poly}}(\log\log n)$
factors due to a lower bound of $\Omega(\log n/\log\log n)$ by earlier work of
Bafna, Srinivasan, and Sudan [BSS20]. Using further ideas, we also extend the
algorithm from Theorem 1.1 to the list decoding regime. For this, we need
first a combinatorial list decoding bound.

######  Theorem 1.2 (Combinatorial list decoding bound for $\mathcal{P}_{1}$).

For any constant $\varepsilon>0$, the space $\mathcal{P}_{1}$ over any Abelian
group $G$ is $(1/2-\varepsilon,\mathop{\mathrm{poly}}(1/\varepsilon))$-list
correctable.

Using the combinatorial list decoding bound, we also give a local list
correction algorithm for degree $1$ polynomials. We state the result below.
For a formal definition of local list correction, refer to Definition 2.

######  Theorem 1.3 (Local List Correction for degree-$1$).

There exists a fixed polynomial $L$ such that for all Abelian groups $G$ and
for every $\varepsilon>0$ and $n\in\mathbb{Z}^{+}$ we have that
$\mathcal{P}_{1}(\\{0,1\\}^{n},G)$ is
$(1/2-\varepsilon,L(\varepsilon),\widetilde{O}(\log n))$-locally list
correctable.

Specifically, there is a randomized algorithm $\mathcal{A}$ that, when given
oracle access to a polynomial $f$ and a parameter $\varepsilon>0$, outputs
with probability at least $3/4$ a list of randomized algorithms
$\phi_{1},\ldots,\phi_{L}$ ($L\leq\mathop{\mathrm{poly}}(1/\varepsilon)$) such
that the following holds:

For each $P\in\mathcal{P}_{1}$ that is $(1/2-\varepsilon)$-close to $f$, there
is at least one algorithm $\phi_{i}$ that, when given oracle access to $f$,
computes $P$ correctly on every input with probability at least $3/4.$

The algorithm $\mathcal{A}$ makes $O_{\varepsilon}(1)$ queries to $f$, while
each $\phi_{i}$ makes $\tilde{O}_{\varepsilon}(\log n)$ queries to $f.$

Using known local testing results [BSS20, ASS23], one can show that the local
list-correction Theorem 1.3 actually implies Theorem 1.1. Nevertheless, we
present the proof of Theorem 1.1 in its entirety, since it is a simpler self-
contained proof than the one that goes through Theorem 1.3, and introduces
some of the same ideas in an easier setting. A weak version of Theorem 1.1 is
also required for Theorem 1.3.

###  1.3 Proof Overview

####  1.3.1 Local Correction - Theorem 1.1

We prove Theorem 1.1 in three steps. The first step, which is specific to the
space of linear polynomials, shows how to locally correct from any oracle $f$
that $\mathcal{O}(1/\log n)$-close to a degree-$1$ polynomial in $n$ variables
using $O(\log n)$ queries. In the second and third steps, we show how to
increase the radius of decoding from $\mathcal{O}(1/\log n)$ to an absolute
constant and then to (nearly) half the unique decoding radius. The latter two
steps also work for polynomials of degree greater than $1.$

##### First step

To motivate the proof of the first step, it is worth recalling the idea behind
the lower bound result of [BSS20] mentioned above. For simplicity, let us
assume that we are working with _homogeneous_ linear polynomials over
$\mathbb{R}$. In this situation, we can equivalently replace the domain with
$\\{-1,1\\}^{n}.$ Now, assume the given oracle
$f:\\{-1,1\\}^{n}\rightarrow\mathbb{R}$ agrees with some homogeneous linear
polynomial $P$ at all points of Hamming weight in the range
$[\frac{n}{2}-n^{0.51},\frac{n}{2}+n^{0.51}]$, and takes adversarially chosen
values outside this set. It is easy to check that $f$ is
$\exp\left(-n^{\Omega(1)}\right)$-close to $P$. Further, assume that we only
want to correct the polynomial $P$ at the point $1^{n}.$

Over $\mathbb{R}$, the space of homogeneous linear polynomials forms a vector
space. Hence, given access to an oracle $f$ that is close to a codeword $P$,
it is natural to correct $P$ using a ‘linear algorithm’ in the following
sense. To correct $P$ at $1^{n}$, we choose points
$\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(q)}\in\\{-1,1\\}^{n}$ and output

$c_{1}f(\mathbf{x}^{(1)})+\cdots+c_{q}f(\mathbf{x}^{(q)})$

for some coefficients $c_{1},\ldots,c_{q}\in\mathbb{R}.$ (Indeed, it is not
hard to argue that if any strategy works, then there must be a linear
algorithm that does [BSS20].)

Since this strategy must work when given $P$ itself as an oracle, it must be
the case that

$P(1^{n})=c_{1}P(\mathbf{x}^{(1)})+\cdots+c_{q}P(\mathbf{x}^{(q)})$

for any linear polynomial $P$. Further, as the space of homogeneous linear
polynomials is a vector space spanned by the coordinate (i.e. dictator)
functions, it is necessary and sufficient to have

$1^{n}=c_{1}\cdot\mathbf{x}^{(1)}+\cdots+c_{q}\cdot\mathbf{x}^{(q)}.$ (1)

Finally, for such a correction algorithm to work for $f$ as given above, it
must be the case that each of the ‘query points’
$\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(q)}$ has Hamming weight in the range
$[n/2-n^{0.51},n/2+n^{0.51}]$.

Note that Equation 1 cannot hold for _perfectly balanced_ (i.e. Hamming weight
exactly $n/2$) query points, no matter what $q$ we choose: this is because the
query points lie in a subspace not containing $1^{n}.$ The work of [BSS20]
showed a robust version of this: for any set of ‘nearly-balanced’ vectors with
Hamming weight in the range $[n/2-n^{0.51},n/2+n^{0.51}]$ that satisfy
Equation 1, it must hold that $q=\Omega(\log n/\log\log n).$ At a high level,
this lower bound holds because if Equation 1 is true, then the coefficients
can be taken to be at most $q^{\mathcal{O}(q)}$ in magnitude (via a suitable
application of Cramer’s rule). The lower bound then follows by adding up the
entries of the vectors on both sides of Equation 1.

The first step of the algorithm is based on showing that this lower bound is
essentially tight. More formally, we show that we can find $q=\mathcal{O}(\log
n)$ nearly-balanced111In fact, the vectors we construct have Hamming weight
$n/2\pm 1$. vectors $\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(q)}\in\\{0,1\\}^{n}$
such that the following (more general) equation holds.

$1^{n+1}=c_{1}\cdot\left(\begin{array}[]{c}1\\\
\mathbf{x}^{(1)}\end{array}\right)+\cdots+c_{q}\cdot\left(\begin{array}[]{c}1\\\
\mathbf{x}^{(q)}\end{array}\right).$ (2)

This identity allows us to correct any linear (not just homogeneous)
polynomial. Moreover, we show that we can take the coefficients to be
_integers_ , which allows us to apply this algorithm over any Abelian
group.222It makes sense to multiply a group element $g$ with an integer $k$,
since it amounts to adding either the element $g$ or its inverse $-g$, $|k|$
times.

Finally, we show that this construction also implies a similar algorithm to
compute $P(1^{n})$ from _any_ $f$ that is $\mathcal{O}(1/\log n)$-close to $P$
(and not just the special $f$ given above). This is done by constructing
random query points $\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)}$ where the $i$th
bit of these vectors is picked by choosing a _random_ bit of
$\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(q)}$. The fact that each
$\mathbf{x}^{(j)}$ is nearly balanced implies that each $\mathbf{y}^{(j)}$ is
nearly uniform over $\\{0,1\\}^{n}$ and hence likely not an error point of
$f.$ Intuitively, the distance requirement is because we make $q$ (nearly)
random queries to $f$ and the algorithm succeeds if none of the query points
is in error. So, the algorithm correctly computes $P(1^{n})$ when
$\delta(f,P)$ is sufficiently smaller than $1/q$. By a suitable ‘shift’, we
can also correct at points other than $1^{n}.$

This construction of the points
$\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(q)}\in\\{0,1\\}^{n}$ is based on
ensuring that the coefficients $c_{1},\ldots,c_{q}$ must be exponentially
large in $q$ (to ensure that the argument of [BSS20] is tight). This leads to
the natural problem of finding a hyperplane whose Boolean solutions cannot be
described by an equation with small coefficients. This is a topic that has
received much interest in the study of threshold circuits and combinatorics
[GHR92, H9̊4, AVu97, Pod09, BHPS10].

For the result stated above, we require only a simple construction. Consider
the following equation over $\\{0,1\\}^{q}$ where $q=2k$. The first $k$ bits
describe an integer $i\in\\{0,\ldots,2^{k}-1\\}$ and the last $k$ bits
describe an integer $j.$ The hyperplane expresses the constraint that $j=i-1.$
This hyperplane can easily be described using coefficients that are
exponentially large in $k$ and one can easily show that this is in fact
necessary. After some modification to ensure that the coefficients sum to $1,$
we get Equation 2. See Lemma 3.4 for more details.

Using a more involved construction due to Håstad [H9̊4] and its extension due
to Alon and Vu [AVu97], it is possible to show that we can achieve $q=O(\log
n/\log\log n)$, showing that the lower bound of [BSS20] is in fact tight up to
constant factors (see Appendix B). However, in this case, we don’t know how to
ensure that the coefficients $c_{1},\ldots,c_{q}$ are integers, meaning that
the algorithm does not extend to general Abelian groups.333Moreover, we also
lose $\mathop{\mathrm{poly}}(\log\log n)$ factors in query complexity in the
subsequent steps, and so the final algorithm is only tight up to
$\mathop{\mathrm{poly}}(\log\log n)$ factors, no matter which construction we
use in the first step.

##### Second and third steps

To obtain an algorithm resilient to a larger fraction of errors, we use a
process of error reduction. Specifically, we show that, given an oracle
$f:\\{0,1\\}^{n}\rightarrow G$ that is $\delta$-close to a polynomial
$P\in\mathcal{P}_{1}$, we can obtain (with high probability) an oracle
$g:\\{0,1\\}^{n}\rightarrow G$ that is $\mathcal{O}(1/\log n)$-close to $P$;
we can then apply the above described local correction algorithm to $g$ to
correct $P$ at any given point. The oracle $g$ makes
$\mathop{\mathrm{poly}}(\log\log n)$ queries to $f$ and hence the overall
number of queries to $f$ is $\tilde{\mathcal{O}}(\log n).$

Interestingly, the error-reduction step is not limited to linear polynomials.
We show that this also works for the space of degree-$d$ polynomials, where
the number of queries now also depends on the degree parameter $d.$ In
general, $\delta$ can be arbitrarily close to the unique decoding radius of
$\mathcal{P}_{d}$, which is $2^{-(d+1)}.$

We use two slightly different error-reduction algorithms to handle the case
when $\delta$ is a small constant, and the case when $\delta$ is close to
$2^{-(d+1)}$ respectively. We reduce the latter case to the former case and
the former to the case of error $\mathcal{O}(1/\log n).$ It is simpler to
describe the error reduction algorithm when the error is large, i.e. close to
the unique decoding radius, so we start there.

The process of error-reduction may be viewed as an _average-case_ version of
the correction problem, where we are only required to compute $P$ on _most_
points in $\\{0,1\\}^{n}$ with high probability. Assume, therefore, that we
are given a _random_ point $\mathbf{a}\in\\{0,1\\}^{n}$ and we are required to
output $P(\mathbf{a})$ (with high probability).

In the setting where the domain is not $\\{0,1\\}^{n}$ but rather a vector
space like $\mathbb{F}_{q}^{n}$, a natural strategy going back to the works of
Beaver and Feigenbaum [BF90] and Lipton [Lip89] is to choose a random subspace
$V$ of appropriate constant444Here, we think of all parameters except $n$ as
constants. dimension $k$ containing $\mathbf{a}$ and then find the closest
$k$-variate degree-$d$ polynomial to the restriction $f|_{V}$ of $f$ to this
subspace. The reason this works is that the points in a random subspace come
from a pairwise independent distribution and hence standard second-moment
methods show that $\delta(f|_{V},P|_{V})\approx\delta$ with high probability,
in which case $\delta(f|_{V},P|_{V})$ is also less than the unique-decoding
radius of $\mathcal{P}_{d}.$ A brute-force algorithm (or better ones, such as
the Welch-Berlekamp algorithm (see e.g. [GRS23, Chapter 15])) can now be used
to find $P|_{V}$, which also determines $P(\mathbf{a}).$

To adapt this idea to the setting of $\\{0,1\\}^{n}$, we note that random
subspaces are not available to us since most constant-dimensional subspaces
don’t have points in $\\{0,1\\}^{n}$. However, we observe that we can apply
the above idea to a _random subcube_ in $\\{0,1\\}^{n}.$ More specifically, we
identify variables randomly into $k$ buckets via a random hash function
$h:[n]\rightarrow[k]$, reducing the original set of $n$ variables
$x_{1},\ldots,x_{n}$ to a set of $k$ variables $y_{1},\ldots,y_{k}.$ Further,
to ensure that the given point $\mathbf{a}$ is in the chosen subcube, we start
by replacing $x_{i}$ by $x_{i}\oplus a_{i}$ before the identification
process.555The process of XORing a variable $x$ by a Boolean value $b$ is
equivalent to either leaving the variable as is when $b=0$, or replacing $x$
by $1-x$ when $b=1$. This does not affect the degree of the polynomial $P.$
This gives rise to a random subcube $\mathsf{C}$ containing $\mathbf{a}$
(obtained by setting $y_{1}=\cdots=y_{k}=0$). We define a random subcube
formally in Definition 5. We can now apply the above idea by restricting the
given $f$ to this subcube.

Having defined a subcube $\mathsf{C}$ as above, the non-trivial part of the
argument is to show that
$\delta(f|_{\mathsf{C}},P|_{\mathsf{C}})\approx\delta$. This is not obvious as
the points of the subcube $\mathsf{C}$ are not pairwise independent.
Nevertheless, for random $\mathbf{a}$, the points of $\mathsf{C}$ are ‘noisy’
copies of one another (Definition 4). Using this fact and standard
hypercontractivity estimates, we can show that most pairs of points of $C$ are
‘approximately’ pairwise independent (see Theorem 2.3 below) as long as $k$ is
a large enough constant. This allows us to use the second-moment method to
recover $P(\mathbf{a})$ as before, for all but a small fraction
$\delta^{\prime}$ of possible inputs $\mathbf{a}$ (with high probability). The
parameter $k$ is $\mathop{\mathrm{poly}}(1/\delta^{\prime})$ and hence the
query complexity is constant as long as the required error $\delta^{\prime}$
is constant. This step is proved in Section 3.2.

To reduce the error further down to $\mathcal{O}(1/\log n)$, we modify the
above idea. We repeat the above process666Actually, we need to slightly modify
the process to ensure that we only query ‘balanced’ points on the subcube
$\mathsf{C}$. We postpone this detail to the proof. on three randomly chosen
subcubes of dimension $k^{\prime}$ each containing $\mathbf{a}$ and take a
plurality vote of their outputs. The probability of error in this algorithm is
bounded by the probability that at least two of the iterations query a point
of error, which would be $\leq\mathcal{O}_{k^{\prime}}((\delta^{\prime})^{2})$
if the repetitions were entirely independent. However, the iterations here
have some dependency - each iteration uses the _same_ random input
$\mathbf{a}.$ Nevertheless, using hypercontractivity, we can again argue that
if $k^{\prime}$ is a large enough constant _depending only on $d$_, the
probability of error is at most
$\mathcal{O}_{k^{\prime}}((\delta^{\prime})^{1.5})\leq(\delta^{\prime})^{1.1}$
for small enough $\delta^{\prime}.$ Repeating this process $t$ times, gives an
error that is _double-exponentially_ small in $t$, at the expense of
$\mathcal{O}_{k^{\prime}}(1)^{t}$ many queries. Choosing $t$ to be
$\mathcal{O}(\log\log\log n)$ gives us an oracle that is $\mathcal{O}(1/\log
n)$-close to $P.$ This step is proved in Section 3.3.

####  1.3.2 Combinatorial List Decoding Bound - Theorem 1.2

We first note that the list size can indeed be as large as
$\mathop{\mathrm{poly}}(1/\varepsilon)$, no matter the underlying group $G.$
This is shown by the following example. Fix an integer parameter $t$ and any
non-zero elment $g\in G$. Let $f=\mathrm{Maj}_{G}^{t}(x_{1},\ldots,x_{t})$
denote the function of the first $t$ input variables that takes the value $g$
when it’s input has Hamming weight greater than $t/2$ and the value $0$
otherwise. A standard calculation (see e.g. [O’D14, Theorem 5.19]) shows that
$\mathrm{Maj}_{G}^{t}$ agrees with the linear functions $g\cdot x_{i}$
($i\in[t]$) on a $(\frac{1}{2}+\frac{O(1)}{\sqrt{t}}$)-fraction of inputs.
Setting $t=\Theta(1/\varepsilon^{2}),$ we see that this agreement can be made
$\frac{1}{2}+\varepsilon.$ This implies that for $f$ as defined above, the
list size at distance $\frac{1}{2}-\varepsilon$ can be as large as
$\Omega((1/\varepsilon)^{2})).$

To motivate the proof of Theorem 1.2, it is helpful to start with the case
when $G$ is a group $\mathbb{Z}_{p}$ of prime order. There are two extremes in
this case: $p=2$ and large $p$ (say a large constant or even growing with
$n$).

##### Case 1: $p=2$

The case $p=2$ is the classical setting that has been intensively investigated
in the literature, starting with the foundational work of Goldreich and Levin
[GL89] (see also the work of Kushilevitz and Mansour [KM93]). In this setting,
it is well-known that the bound of $1/\varepsilon^{2}$ is tight. This follows
from the standard Parseval identity from basic Fourier analysis of Boolean
functions (see e.g. [O’D14]) or as a special case of the binary Johnson bound
(see e.g. the appendix of [DGKS08]). At a high level, this is because the
Boolean Fourier transform identifies each
$f:\\{0,1\\}^{n}\rightarrow\mathbb{Z}_{2}$ with a real unit vector
$\mathbf{v}_{f}$ such that distinct linear polynomials are mapped to an
orthonormal basis. Moreover, if $f$ is $(\frac{1}{2}-\varepsilon)$-close to a
linear polynomial $P$, then the length of projection of the vector
$\mathbf{v}_{f}$ on $\mathbf{v}_{P}$ is at least $\varepsilon$. Pythagoras’
theorem now implies the list bound.

##### Case 2: Large $p$

For $p>2$, it is unclear if we can map distinct linear polynomials to
orthogonal real or complex vectors in the above way. Nevertheless, we do
expect the list-size bound to hold, as the distance $\delta(\mathcal{P}_{1})$
is the same as over $\mathbb{Z}_{2}$, i.e. $1/2$. Moreover, a _random_ pair of
linear polynomials have a distance much larger than $1/2$ for large $p.$ This
latter fact is a consequence of _anti-concentration_ of linear polynomials,
which informally means the following. Let $P(\mathbf{x})$ be a non-zero
polynomial with many (say, at least $100$) non-zero coefficients. Then, on a
random input $\mathbf{a}$, the random variable $P(\mathbf{a})$ does not take
any given value $b\in\mathbb{Z}_{p}$ with good probability (say, greater than
$1/5$).

In the case of large $p$, we crucially use anti-concentration to argue the
upper bound on the list size. At a high level, in this case, we can show that
if a function $f:\\{0,1\\}^{n}\rightarrow\mathbb{Z}_{p}$ is
$(\frac{1}{2}-\varepsilon)$-close to many (say $L$) linear polynomials, then
there is a large subset (size $L^{\prime}=L^{\Omega(1)}$) that ‘look’ somewhat
like the example of the $\mathrm{Maj}_{G}^{t}$ example mentioned above. More
precisely, the coefficient vectors of the linear polynomials in this subset
are at most a _constant_ (independent of $p$, order of the underlying group)
Hamming distance from one another. By shifting the polynomials by one of the
linear functions in the subset, we can assume without loss of generality that
all the linear functions in fact have a constant number of _non-zero
coefficients_ , as in the case of the list of polynomials corresponding to
$\mathrm{Maj}_{G}^{t}.$ It now suffices to bound the size $L^{\prime}$ of this
subset by $\mathop{\mathrm{poly}}(1/\varepsilon).$

The bound now reduces to a case analysis based on the number of variables that
appear in the coefficients of the $L^{\prime}$ polynomials in the subset. The
case analysis is based on carefully interpolating between the following two
extreme cases.

  * •

The first is that all the $L^{\prime}$ polynomials and also the function $f$
itself depend on the _same_ set of variables. Assume this set is
$S=\\{x_{1},\ldots,x_{\ell}\\}$ where $\ell$ must be a constant (based on the
previous paragraph). In this case, we note that each polynomial $P$ in the
list is specified completely by the subset of $A\subseteq\\{0,1\\}^{\ell}$
where $P$ agrees with $f$ (by the fact that $\delta(\mathcal{P}_{1})=1/2$).
Since the number of such $A$ is at most $2^{2^{\ell}}$, this bounds
$L^{\prime}$ by the same quantity.

  * •

The other extreme case is that the polynomials in the list all depend on
_disjoint_ sets of variables. In this case, on a random input
$\mathbf{a}\in\\{0,1\\}^{n}$, the polynomials in the list all output
_independent_ random values in $\mathbb{Z}_{p}$. By a Chernoff bound, it is
easy to argue that the chance that significantly more than
$\frac{L^{\prime}}{2}+\sqrt{L^{\prime}}$ of these polynomials agree with
$f(\mathbf{a})$ is very small. By an averaging argument, this implies that
$L^{\prime}$ is $\tilde{\mathcal{O}}(1/\varepsilon^{2})$, and we are done.

##### Putting it together

We sketch here how to handle general finite Abelian groups. In the proof, we
show that this also implies the same bound for infinite groups such as
$\mathbb{R}$.

Recall that any finite group $G$ is a direct product of cyclic groups, each of
which has a size that is a prime power. We collect the terms in this product
to write $G=G_{1}\times G_{2}\times G_{3}$ where $G_{1}$ is the product of the
factors of sizes that are powers of $2,$ $G_{2}$ is the same with powers of
$3$, and $G_{3}$ is the product of the rest.777There is nothing very special
about this decomposition. Essentially, we have one argument that works for
‘small’ $p$ and another that works for ‘large’ $p$. To combine them, we need
some formalization of these notions. Here, ‘large’ could be defined to be
larger than any constant $C\geq 5.$ A simple observation shows that it
suffices to bound the size of the list in each of these cases by
$\mathop{\mathrm{poly}}(1/\varepsilon).$

For $G_{3},$ the argument of large $p$ sketched above works without any change
(with some care to ensure that we can handle all the primes greater than or
equal to $5$). The only part of the argument that is sensitive to the choice
of the group is the initial use of anti-concentration, and this works over
$G_{3}$ since the order of any non-zero element is large (i.e. at least $5$).

The argument for $G_{1}$ needs more work. While the use of Parseval’s identity
works over $\mathbb{Z}_{2}$, it is not clear how to extend it to groups of
size powers of $2$, such as $\mathbb{Z}_{4}.$ For inspiration, we turn to a
different extension of the $\mathbb{Z}_{2}$-case proved by Dinur, Grigorescu,
Kopparty, and Sudan [DGKS08]. They deal with the list-decodability of the
space of _group homomorphisms_ from a group $H$ to a group $G$. Setting the
group $H$ to be $\\{0,1\\}^{n}$ (with addition defined by the XOR operation)
and $G$ to be $\mathbb{Z}_{2},$ we recover again the setting of (homogeneous)
linear polynomials over $\mathbb{Z}_{2}.$ The work of [DGKS08] show how to
extend this result to larger groups $G$ that have order a power of $2$. Note
that it is not immediately clear that this should carry over to the setting of
linear polynomials: for groups of order greater than $2$, the space of
polynomials is different from the space of homomorphisms. However, we show
that the technique of [DGKS08] does work in our setting as well.

Finally, the proof for $G_{2}$ is a combination of the ideas of the two proofs
above. We omit the details here and refer the reader to the actual proof.

####  1.3.3 Local List Correction - Theorem 1.3

Like the proof of the second and third steps of Theorem 1.1 described above,
at the heart of our local list correction algorithm lies an error-reduction
algorithm. More precisely, we design an algorithm $\mathcal{A}_{1}^{f}$ which,
using oracle access to $f$, produces a list of algorithms
$\psi_{1},\ldots,\psi_{L}$ such that, with high probability, for each linear
polynomial $P$ that is $(\frac{1}{2}-\varepsilon)$-close to $f$, there is at
least one algorithm $\psi_{j}$ in the list that agrees with $P$ on _most_
inputs, i.e. $\psi_{j}$ “approximates” $P$. Here, $L\leq L(\varepsilon)$
denotes the list-size bound proved in Theorem 1.2. Further, each $\psi_{i}$
makes at most $O_{L}(1)=O_{\varepsilon}(1)$ queries to $f$.

We can now apply the algorithm from the unique correction setting with oracle
access to the various $\psi_{j}$ to produce the desired list
$\phi_{1},\ldots,\phi_{L}$ as required.

The proof is motivated by a local list-decoding algorithm for low-degree
polynomials over $\mathbb{F}_{q}^{n}$ due to Sudan, Trevisan, and Vadhan
[STV01]. In that setting, we are given oracle access to a function
$f:\mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}$ and we are required to produce
a list as above that approximates the set $S=\\{P_{1},\ldots,P_{L}\\}$ of
degree-$d$ polynomials (say $d=o(q)$) that have significant (say $\Omega(1)$)
agreement with $f$. It follows from the Johnson bound that $L=\mathcal{O}(1)$
in this case (see, e.g. [GRS23, Chapter 7]). The corresponding algorithm
$\mathcal{A}_{\mathrm{STV}}$ chooses a _random_ point $\mathbf{a}$ and gets as
advice the values of $\alpha_{i}=P_{i}(\mathbf{a})$ for each $i\in[L]$. (We
can easily get rid of this advice assumption, but let us assume for now that
we have it.)

Now, we want to produce an algorithm that approximates $P_{i}$. Given a random
point $\mathbf{b}\in\mathbb{F}_{q}^{n}$, the algorithm constructs the random
line $\ell$ passing through $\mathbf{a}$ and $\mathbf{b}$ and produces the
list of univariate polynomials that have significant agreement with the
restriction $f|_{\ell}$ of $f$ to the line. This can be done via brute force
with $O(d)$ queries (if one only cares about query complexity) or in
$\mathop{\mathrm{poly}}(d,\log q)$ time using Sudan’s list decoding algorithm
for univariate polynomials [Sud97]. By pairwise independence and standard
second-moment estimates, it is easy to argue that for each $j\in[L]$,
$P_{j}|_{\ell}$ is in this list of univariate polynomials. However, to single
out $P_{i}|_{\ell}$ in this list, we use advice
$\alpha_{i}=P_{i}(\mathbf{a})$. Since $\mathbf{a}$ is a _random_ point on
$\ell$ (even given $\ell$), it follows that, with high probability,
$\alpha_{i}$ uniquely disambiguates $P_{i}|_{\ell}$ from the ($\mathcal{O}(1)$
many) other polynomials in the list. In particular this also determines
$P_{i}(\mathbf{b})$, since $\mathbf{b}$ lies on $\ell$.

Let us now turn to our local list correction algorithm. We use similar ideas
to [STV01] but, as in the proof of Theorem 1.1, with _subcubes_ instead of
lines. More precisely, the algorithm $\mathcal{A}_{1}^{f}$ produces a random
$\mathbf{a}$ and a random hash function $h:[n]\rightarrow[k]$
($k=\mathcal{O}_{\varepsilon}(1)$ suitably large), and uses them to produce a
random subcube $\mathsf{C}$ as in the proof sketch of Theorem 1.1. The advice
in this case is the restriction $P|_{\mathsf{C}}$ for each polynomial $P$ in
the set $S=\\{P_{1},\ldots,P_{L}\\}$ of degree-$1$ polynomials that are
$(\frac{1}{2}-\varepsilon)$-close to $f$.

Now, given a random point $\mathbf{b}\in\\{0,1\\}^{n}$, we correct
$P_{i}(\mathbf{b})$ as follows. We first construct the smallest subcube
$\mathsf{C^{\prime}}$ that contains both $\mathsf{C}$ and the point
$\mathbf{b}$. With high probability, this is a subcube of dimension $2k$.
Using a simple brute-force algorithm that uses $2^{2k}$ queries to $f$, we can
find the set $S^{\prime}$ of all $2k$-variate linear polynomials that are
$(\frac{1}{2}-\frac{\varepsilon}{2})$-close to $f|_{\mathsf{C^{\prime}}}$.
Note that $|S^{\prime}|\leq L(\varepsilon).$ By a hypercontractivity-based
argument (as we did in the error reduction algorithms), we can show that, with
high probability, each $P_{j}|_{\mathsf{C^{\prime}}}$ is in this list
$S^{\prime}$. To single out $P_{i}|_{\mathsf{C^{\prime}}}$, we use advice
$P_{i}|_{\mathsf{C}}$. The proof that this works needs an understanding of the
distribution of $\mathsf{C}$ given $\mathsf{C^{\prime}}$: it turns out that
the $k$-dimension subcube $\mathsf{C}$ is obtained by randomly pairing up
variables in $\mathsf{C^{\prime}}$ and identifying them with a single
variable. We show that, if $k$ is large enough in comparison to the list bound
$L$, then with high probability, this process does not identify any two
distinct elements in the list.888There is a small subtlety in the argument
that is being hidden here for simplicity. Thus, we are able to single out
$P_{i}|_{\mathsf{C^{\prime}}}$ and this allows us to compute
$P_{i}(\mathbf{b})$ correctly, with high probability over the choice of
$\mathbf{b}$ and the randomness of the algorithm (which includes $\mathbf{a}$
and the hash function $h$).

Finally, to get rid of the advice, we note that a similar hypercontractivity-
based argument also shows that each $P_{i}|_{\mathsf{C}}$ is
$(\frac{1}{2}-\frac{\varepsilon}{2})$-close to $f|_{\mathsf{C}}$. So by
applying a similar brute-force algorithm on $\mathsf{C}$, we find, with high
probability, a set $\tilde{S}$ of polynomials containing $P_{i}|_{\mathsf{C}}$
for each $i\in[L]$. This is good enough for the argument above. The algorithm
$\mathcal{A}_{1}^{f}$ first computes $\tilde{S}$ and then outputs the
descriptions of the algorithm in the previous paragraph for each
$P\in\tilde{S}$ (treating it as a restriction of one of the $P_{i}$).

##  2 Preliminaries

###  2.1 Notation

Let $(G,+)$ denote an Abelian group $G$ with addition as the binary operation.
For any $g\in G$, let $-g$ denote the inverse of $g\in G$. For any $g\in G$
and integer $a\geq 0$, $a\cdot g$ (or simply $ag$) is the shorthand notation
of $\underbrace{g+\ldots+g}_{a\;\mathrm{times}}$ and $-ag$ denotes
$a\cdot(-g).$

For a natural number $n$, we consider functions $f:\\{0,1\\}^{n}\to G$. We
denote the set of functions that can be expressed as a multilinear polynomial
of degree $d$, with the coefficients being in $G$ by $\mathcal{P}_{d}(n,G)$.
We will simply write $P_{d}$ when $n$ and $G$ are clear from the context. For
$\mathbf{x},\mathbf{y}\in\\{0,1\\}^{n}$, let $\delta(\mathbf{x},\mathbf{y})$
denote the relative Hamming distance between $\mathbf{x}$ and $\mathbf{y}$,
i.e. $\delta(\mathbf{x},\mathbf{y})=|\left\\{i\in[n]\;\middle|\;x_{i}\neq
y_{i}\right\\}|/n$.

For any $\mathbf{x}\in\\{0,1\\}^{n}$, $|\mathbf{x}|$ denotes the Hamming
weight of $\mathbf{x}$. $\tilde{O}(\cdot)$ notation hides factors that are
poly-logarithmic in its argument. For a polynomial $P(\mathbf{x})$, let
$\mathrm{vars}(P)$ denote the variables on which $P$ depends, i.e. the
variables that appear in a monomial with non-zero coefficient in $P$.

For any natural number $n$, $U_{n}$ denotes the uniform distribution on
$\\{0,1\\}^{n}$.

###  2.2 Basic Definitions and Tools

##### Probabilistic notions.

For any distribution $X$ on $\\{0,1\\}^{n}$, let $\mathrm{supp}(X)$ denote the
subset of $\\{0,1\\}^{n}$ on which $X$ takes non-zero probability. For two
distributions $X$ and $Y$ on $\\{0,1\\}^{n}$, the statistical distance between
$X$ and $Y$, denoted by $\mathrm{SD}(X,Y)$ is defined as

$\displaystyle\mathrm{SD}(X,Y)=\max_{T\subseteq\\{0,1\\}^{n}}|\Pr[X\in
T]-\Pr[Y\in T]|$

We say $X$ and $Y$ are $\varepsilon$-close if the statistical distance between
$X$ and $Y$ is at most $\varepsilon$.

##### Coding theory notions.

Fix an Abelian group $G$. We use $\mathcal{P}_{d}$ to denote the space of
multilinear polynomials from $\\{0,1\\}^{n}$ to $G$ of degree at most $d.$
More precisely, any element $P\in\mathcal{P}_{d}$ can be described as

$P(x_{1},\ldots,x_{n})=\sum_{I\subseteq[n]\,:\,|I|\leq d}\alpha_{I}\prod_{i\in
I}x_{i}$

where $\alpha_{I}\in G$ for each $I.$ On an input
$\mathbf{a}\in\\{0,1\\}^{n}$, each monomial evaluates to a group element in
$G$ and the polynomial evaluates to the sum of these group elements.

The following is a summary of standard facts about multilinear polynomials,
which also hold true in the setting when the range is an arbitrary Abelian
group $G.$ The proofs are standard and omitted.

######  Theorem 2.1.

  1. 1.

(Möbius Inversion) Any function $f:\\{0,1\\}^{n}\rightarrow G$ has a unique
representation as a multilinear polynomial in $\mathcal{P}_{n}$. Moreover, we
have $f=\sum_{I\subseteq[n]}c_{I}\prod_{i\in I}x_{i}$ where for any
$I\subseteq[n],$ we have

$c_{I}=\sum_{J\subseteq I}(-1)^{|I\setminus J|}f(1_{J})$

where $1_{J}$ is the indicator vector of the set $J.$

  2. 2.

(DeMillo-Lipton-Schwartz-Zippel) Any non-zero polynomial $P\in\mathcal{P}_{d}$
is non-zero with probability at least $2^{-d}$ at a uniformly random input
from $\\{0,1\\}^{n}.$ Equivalently, $\delta(\mathcal{P}_{d})\geq 2^{-d}.$

We now turn to the kinds of algorithms we will consider. Below, let
$\mathcal{F}$ be any space of functions mapping $\\{0,1\\}^{n}$ to $G.$

######  Definition 1 (Local Correction Algorithm).

We say that $\mathcal{F}$ has a $(\delta,q)$-local correction algorithm if
there is a probabilistic algorithm that, when given oracle access to a
function $f$ that is $\delta$-close to some $P\in\mathcal{F}$, and given as
input some $\mathbf{a}\in\\{0,1\\}^{n}$, returns $P(\mathbf{a})$ with
probability at least $3/4.$ Moreover, the algorithm makes at most $q$ queries
to its oracle.

######  Definition 2 (Local List-Correction Algorithm).

We say that $\mathcal{F}$ has a $(\delta,q_{1},q_{2},L)$-local list correction
algorithm if there is a randomized algorithm $\mathcal{A}$ that, when given
oracle access to a function $f$, produces a list of randomized algorithms
$\phi_{1},\ldots,\phi_{L}$, where each $\phi_{i}$ has oracle access to $f$ and
have the following property: with probability at least $3/4$, for each
codeword $P$ that is $\delta$-close to $f$, there exists some $i\in[L]$ such
that the algorithm $\phi_{i}$ computes $P$ with error at most $1/4$, i.e. on
any input $\mathbf{a}$, the algorithm $\phi_{i}$ outputs $P(\mathbf{a})$ with
probability at least $3/4$.
Moreover, the algorithm $\mathcal{A}$ makes at most $q_{1}$ queries to $f$,
while the algorithms $\phi_{1},\ldots,\phi_{L}$ each make at most $q_{2}$
queries to $f$.

######  Remark 2.2.

Our algorithms can all be implemented as standard Boolean circuits with the
added ability to manipulate elements of the underlying group $G$.
Specifically, we assume that we can store group elements, perform group
operations (addition, inverse) and compare two group elements to check if they
are equal.

######  Definition 3 (Combinatorial List Decodability).

We say that $\mathcal{F}$ is $(\delta,L)$-list decodable if for any function
$f$, the number of elements of $\mathcal{F}$ that are $\delta$-close to $f$ is
at most $L.$

The questions of decoding polynomial-based codes over groups become much more
amenable to known techniques if we drop the locality constraint. In Appendix
A, we show how to modify the standard Majority-logic decoding algorithm to
obtain non-local unique and list-decoding algorithms for $\mathcal{P}_{d}.$

##### Hypercontractivity.

Next we are going to state a consequence of the standard Hypercontracitivity
theorem (Refer to [O’D14, Chapter 9]).

######  Definition 4 (Noise distribution).

Let $\rho\in[-1,1]$. For a fixed $\mathbf{x}\in\\{0,1\\}^{n}$,
$\mathbf{y}\sim\mathcal{N}_{\rho}(\mathbf{x})$ denotes a random variable
defined as follows: For each $i\in[n]$ independently,

$\displaystyle y_{i}:=\begin{cases}x_{i},&\text{with prob. }\,(1+\rho)/2\\\
\neg x_{i},&\text{with prob. }\,(1-\rho)/2\end{cases}$

In other words, to sample from the distribution
$\mathcal{N}_{\rho}(\mathbf{x}))$, we flip each bit of $\mathbf{x}$
independently with probability $(1-\rho)/2$, and keeping it unchanged with
probability $(1+\rho)/2$.

######  Theorem 2.3 ([O’D14, Section 9.5]).

Let $E\subseteq\\{0,1\\}^{n}$ be a subset of density $\delta$, i.e.
$|E|/2^{n}=\delta$. Then for any $\rho\in[-1,1]$,

$\displaystyle\Pr_{\begin{subarray}{c}\mathbf{x}\sim\\{0,1\\}^{n}\\\
\mathbf{y}\sim\mathcal{N}_{\rho}(\mathbf{x})\end{subarray}}[\mathbf{x}\in
E\;\text{and}\;\mathbf{y}\in E]\leq\delta^{2/(1+|\rho|)}$

In particular, if $\rho$ is close to $0$, then Theorem 2.3 tells us that the
probability that $\mathbf{x}$ and $\mathbf{y}$ are in $E$ is close to the
probability in the case that $\mathbf{x}$ and $\mathbf{y}$ are sampled
independently and uniformly from $U_{n}$.

##### Subcubes of $\\{0,1\\}^{n}$.

It will be very useful in our algorithms to be able to restrict the given
function to a small-dimensional subcube and analyze this restriction. We
construct such subcubes by first negating a subset of the variables and then
identifying them into a smaller set of variables. More precisely, we have the
following definition.

######  Definition 5 (Embedding a smaller cube into $\\{0,1\\}^{n}$).

Fix any $k\in\mathbb{N}$ and $k\leq n$. Fix a point
$\mathbf{a}\in\\{0,1\\}^{n}$ and a function $h:[n]\to[k]$. For every
$\mathbf{y}\in\\{0,1\\}^{k}$, $x(\mathbf{y})$ is defined with respect to
$\mathbf{a}$ and $h$ as follows:

$\displaystyle x(\mathbf{y})_{i}=y_{h(i)}\oplus
a_{i}=\begin{cases}a_{i},&\text{if }\,y_{h(i)}=0\\\ 1\oplus a_{i},&\text{if
}\,y_{h(i)}=1\end{cases}$

$C_{\mathbf{a},h}$ is the subset in $\\{0,1\\}^{n}$ consisting of
$x(\mathbf{y})$ for every $\mathbf{y}\in\\{0,1\\}^{k}$, i.e.
$C_{\mathbf{a},h}:=\left\\{x(\mathbf{y})\;\middle|\;\mathbf{y}\in\\{0,1\\}^{k}\right\\}$.

Given any polynomial $P(x_{1},\ldots,x_{n})$ and any subcube
$C_{\mathbf{a},h}$ as above, $P$ restricts naturally to a degree-$d$
polynomial $Q(y_{1},\ldots,y_{k})$ on $C_{\mathbf{a},h}$ obtained by replacing
each $x_{i}$ by $y_{h(i)}\oplus a_{i}$. We use $P|_{C_{\mathbf{a},h}}$ to
denote the polynomial $Q$.

##### Random subcubes.

Now assume that we choose a subcube $C_{\mathbf{a},h}$ by sampling
$\mathbf{a}\sim\\{0,1\\}^{n}$ and sampling a random hash function
$h:[n]\rightarrow[k]$. For any $\mathbf{y}\in\\{0,1\\}^{k}$, $x(\mathbf{y})$
is the image of $\mathbf{y}$ in $\\{0,1\\}^{n}$ under $\mathbf{a}$ and $h$ and
$C_{\mathbf{a},h}$ is the subcube consisting of all $2^{k}$ such images. From
the Definition 5, we can derive following two observations:

  1. 1.

For any $\mathbf{y}\in\\{0,1\\}^{k}$, distribution of $x(\mathbf{y})$ is the
uniform distribution over $\\{0,1\\}^{n}$. This is because $\mathbf{a}$ is
uniformly distributed over $\\{0,1\\}^{n}$.

  2. 2.

Fix $\mathbf{y},\mathbf{y}^{\prime}\in\\{0,1\\}^{k}$. Recall that
$\delta(\mathbf{y},\mathbf{y}^{\prime})$ denotes the fractional Hamming
distance between $\mathbf{y}$ and $\mathbf{y}^{\prime}$. A simple calculation
shows the following: For all $i\in[n]$,

$\displaystyle x(\mathbf{y})_{i}\oplus
x(\mathbf{y}^{\prime})_{i}=\begin{cases}0,&\text{with probability
}\,1-\delta(\mathbf{y},\mathbf{y}^{\prime})\\\ 1,&\text{with probability
}\,\delta(\mathbf{y},\mathbf{y}^{\prime}).\end{cases}$

Since this is true for any choice of $x(\mathbf{y}),$ this means that the
distribution of the random variable $x(\mathbf{y})\oplus
x(\mathbf{y^{\prime}})$ is independent of $x(\mathbf{y})$. In particular,
using also our observation in the previous item, we see that the pair
$(x(\mathbf{y}),x(\mathbf{y}^{\prime}))$ has the same distribution as
$(\mathbf{z},\mathbf{z}^{\prime})$ where $\mathbf{z}$ is chosen uniformly at
random from $\\{0,1\\}^{n}$ and $\mathbf{z}^{\prime}$ is sampled from the
distribution $\mathcal{N}_{\rho}(\mathbf{z}),$ where
$\rho=1-2\delta(\mathbf{y},\mathbf{y}^{\prime}).$

Building on the above observation, we have the following sampling lemma for
subcubes that will be useful at multiple points in the paper.

######  Lemma 2.4 (Sampling lemma for random subcubes).

Sample $\mathbf{a}$ and $h$ uniformly at random, and let
$\mathsf{C}=C_{\mathbf{a},h}$ be the subcube of dimension $k$ as described in
Definition 5. Fix any $T\subseteq\\{0,1\\}^{n}$ and let $\mu:=|T|/2^{n}.$
Then, for any $\varepsilon,\eta>0$

$\displaystyle\Pr_{\mathbf{a},h}\left[\left|\frac{|T\cap\mathsf{C}|}{2^{k}}-\mu\right|\geq\varepsilon\right]<\eta$

as long as
$k\geq\frac{A}{\varepsilon^{4}\eta^{2}}\cdot\log\left(\frac{1}{\varepsilon\eta}\right)$
for a large enough absolute constant $A>0.$

###### Proof.

The proof is an application of the second moment method with a consequence of
the Hypercontractivity theorem (Theorem 2.3) being used to bound the variance.

More formally, for each $\mathbf{y}\in\\{0,1\\}^{k}$, let
$Z_{\mathbf{y}}\in\\{0,1\\}$ be the indicator random variable that is $1$
exactly when $x(\mathbf{y})\in T.$ Let $Z$ denote the sum of all
$Z_{\mathbf{y}}$ ($\mathbf{y}\in\\{0,1\\}^{n})$. The statement of the lemma
may be equivalently stated as

$\Pr_{\mathbf{a},h}\left[\left|Z-\mu\cdot 2^{k}\right|\geq\varepsilon\cdot
2^{k}\right]<\eta$ (3)

for $k$ as specified above.

Since each $x(\mathbf{y})$ is uniformly distributed over $\\{0,1\\}^{n}$, it
follows that each $Z_{\mathbf{y}}$ is a Bernoulli random variable that is $1$
with probability $\mu$. In particular, the mean of $Z$ is $\mu\cdot 2^{k}.$

We now bound the variance of $Z.$ We have, for any $\gamma\in[0,1]$,

$\displaystyle\mathrm{Var}(Z)$
$\displaystyle=\sum_{\mathbf{y},\mathbf{y}^{\prime}}\mathrm{Cov}(Z_{\mathbf{y}},Z_{\mathbf{y}^{\prime}})$
$\displaystyle=\sum_{\begin{subarray}{c}\mathbf{y},\mathbf{y}^{\prime}:\\\
\delta(\mathbf{y},\mathbf{y}^{\prime})\in(\frac{1}{2}-\frac{\gamma}{2},\frac{1}{2}+\frac{\gamma}{2})\end{subarray}}\mathrm{Cov}(Z_{\mathbf{y}},Z_{\mathbf{y}^{\prime}})+\sum_{\begin{subarray}{c}\mathbf{y},\mathbf{y}^{\prime}:\\\
\delta(\mathbf{y},\mathbf{y}^{\prime})\not\in(\frac{1}{2}-\frac{\gamma}{2},\frac{1}{2}+\frac{\gamma}{2})\end{subarray}}\mathrm{Cov}(Z_{\mathbf{y}},Z_{\mathbf{y}^{\prime}})$
$\displaystyle\leq\sum_{\begin{subarray}{c}\mathbf{y},\mathbf{y}^{\prime}:\\\
\delta(\mathbf{y},\mathbf{y}^{\prime})\in(\frac{1}{2}-\frac{\gamma}{2},\frac{1}{2}+\frac{\gamma}{2})\end{subarray}}\mathrm{Cov}(Z_{\mathbf{y}},Z_{\mathbf{y}^{\prime}})+\sum_{\begin{subarray}{c}\mathbf{y},\mathbf{y}^{\prime}:\\\
\delta(\mathbf{y},\mathbf{y}^{\prime})\not\in(\frac{1}{2}-\frac{\gamma}{2},\frac{1}{2}+\frac{\gamma}{2})\end{subarray}}1$
$\displaystyle\leq\sum_{\begin{subarray}{c}\mathbf{y},\mathbf{y}^{\prime}:\\\
\delta(\mathbf{y},\mathbf{y}^{\prime})\in(\frac{1}{2}-\frac{\gamma}{2},\frac{1}{2}+\frac{\gamma}{2})\end{subarray}}\mathrm{Cov}(Z_{\mathbf{y}},Z_{\mathbf{y}^{\prime}})+2^{2k}\cdot\exp(-\Omega(\gamma^{2}k))$

where the final inequality is an application of the Chernoff bound. On the
other hand, for any $\mathbf{y},\mathbf{y}^{\prime}$ such that
$\delta(\mathbf{y},\mathbf{y}^{\prime})\in(\frac{1}{2}-\frac{\gamma}{2},\frac{1}{2}+\frac{\gamma}{2})$,
we have seen above that the pair $(x(\mathbf{y}),x(\mathbf{y}^{\prime}))$ have
the same distribution as a pair of random variables
$(\mathbf{z},\mathbf{z}^{\prime})$ where $\mathbf{z}$ is chosen uniformly at
random from $\\{0,1\\}^{n}$ and $\mathbf{z}^{\prime}$ is sampled from the
distribution $\mathcal{N}_{\rho}(\mathbf{z}),$ where
$\rho=1-2\delta(\mathbf{y},\mathbf{y}^{\prime})\in[-\gamma,\gamma].$

By Theorem 2.3, we see that for such a pair $(\mathbf{y},\mathbf{y}^{\prime})$
and for any $\gamma\leq 1/4,$ we have

$\displaystyle\mathrm{Cov}(Z_{\mathbf{y}},Z_{\mathbf{y}^{\prime}})$
$\displaystyle=\Pr_{\mathbf{a},h}[x(\mathbf{y})\in T\text{ and
}x(\mathbf{y}^{\prime})\in T]-\mu^{2}$
$\displaystyle\leq\mu^{2/1+\gamma}-\mu^{2}\leq\mu^{2(1-\gamma)}-\mu^{2}$
$\displaystyle\leq\min\\{\mu^{1.5},\mu^{2}\cdot(\exp(O(\gamma\cdot\log(1/\mu))-1)\\}.$

Plugging this into the computation above and setting
$\gamma=C_{1}\cdot\sqrt{\frac{\log k}{k}}$ for a large enough absolute
constant $C_{1}$, we get the following inequalities:

$\displaystyle\mathrm{Var}(Z)$ $\displaystyle\leq
2^{2k}\cdot\mu^{1.5}+2^{2k}\cdot\frac{1}{k}\leq 2^{2k}\cdot
O\left(\frac{1}{k}\right)\ \ \ \left(\text{if $\mu\leq\frac{1}{k}$}\right)$
$\displaystyle\mathrm{Var}(Z)$ $\displaystyle\leq 2^{2k}\cdot\mu^{2}\cdot
O\left(\sqrt{\frac{\log
k}{k}}\cdot\log(1/\mu)\right)+2^{2k}\cdot\frac{1}{k}\leq 2^{2k}\cdot
O\left(\sqrt{\frac{\log k}{k}}\right)\ \ \ \left(\text{if
$\mu>\frac{1}{k}$}\right)$

where we used the fact that $e^{x}\leq 1+2x$ for $|x|\leq 1/2$ for the first
inequality and the fact that $\mu\leq 1$ for the second.

Finally, using Chebyshev’s inequality, we get

$\displaystyle\Pr_{\mathbf{a},h}\left[\left|Z-\mu\cdot
2^{k}\right|\geq\varepsilon\cdot 2^{k}\right]$
$\displaystyle=\Pr_{\mathbf{a},h}\left[\left|Z-\operatorname*{\mathbb{E}}[Z]\right|\geq\varepsilon\cdot
2^{k}\right]$
$\displaystyle\leq\frac{\mathrm{Var}(Z)}{\varepsilon^{2}2^{2k}}\leq\frac{1}{\varepsilon^{2}}\cdot
O\left(\sqrt{\frac{\log k}{k}}\right)<\eta$

using the lower bound on $k$ in the statement of the lemma. ∎

##  3 Local Correction in the Unique Decoding Regime

In this section, we will prove Theorem 1.1, i.e. we will give a local
correction algorithm for degree $1$ polynomials with only
$\tilde{\mathcal{O}}(\log n)$ queries.

We will do this in three steps.

  * •

Step 1: We start by proving a slightly weaker statement: we will give a local
correction algorithm that can correct $\mathcal{P}_{1}$ with the error-
parameter $\delta\leq 1/\mathcal{O}(\log n)$ (see Theorem 3.1).

  * •

Step 2: We will show how to handle some $\delta=\Omega(1)$ by reducing to the
small error case (see Section 3.2 and Lemma 3.8).

  * •

Step 3: Using a similar argument to the second step, we prove Theorem 1.1,
which is a local correction algorithm with $\delta$ arbitrarily close to the
unique decoding radius (see Section 3.3 and Lemma 3.13).

The first step works only for linear polynomials, while the latter two
reductions also work for higher-degree polynomials.

###  3.1 Sub-Constant Error

In this subsection, we describe the first step towards proving Theorem 1.1. We
give a local correction algorithm for $\mathcal{P}_{1}$ that can correct for
$\delta<1/\mathcal{O}(\log n)$. The main result of this section is the
following.

######  Theorem 3.1 (Local correction algorithms for $\mathcal{P}_{1}$ up to
error $1/\mathcal{O}(\log n)$).

Let $\mathcal{P}_{1}$ be the set of degree $1$ polynomials from
$\\{0,1\\}^{n}$ to $G$. Then $\mathcal{P}_{1}$ has a $(\delta,q)$-local
correction algorithm for any $\delta<\mathcal{O}(1/\log n)$ and
$q=\mathcal{O}(\log n)$.

######  Remark 3.2.

In [BSS20, Theorem 5.3], a lower bound of $q\geq\Omega(\log n/\log logn)$ was
shown on the number of queries required to locally correct in the setting
where $G$ is the additive group of a field of large characteristic (the lower
bound even holds in the regime $\delta<\exp(-n^{\Omega(1)})$). Our theorem
above implies that this lower bound is tight up to a $\log\log n$ factor in
the setting when $\delta<\mathcal{O}(1/\log n)$. In fact, over the reals, we
can obtain an upper bound of $q=\mathcal{O}(\log n/\log\log n)$, thus matching
the lower bound of [BSS20] up to a constant factor. We refer the reader to
Appendix B for this improvement.

We first describe the general framework of the algorithm, which is applicable
more generally. In the following subsection, we will use this framework for
linear polynomials and construct a local corrector for $\mathcal{P}_{1}$.

####  3.1.1 Framework of Local Correction Algorithm

We will now give a formal definition of how we construct a local correction
algorithm, namely, via a _correction gadget_. This will be useful in the
regime where the distance of the input function to the codeword (in our case,
a linear polynomial) is small.

Let $\mathcal{F}$ be a class of functions from $\\{0,1\\}^{n}$ to an Abelian
group $G$. Let $P_{1},\ldots,P_{D}$ be functions from $\\{0,1\\}^{n}$ to
$\mathbb{Z}$ satisfying the following property: for any $P\in\mathcal{F}$,
there exist coefficients $\alpha_{1},\ldots,\alpha_{D}\in G$ such that for any
$\mathbf{a}\in\\{0,1\\}^{n}$

$\displaystyle
P(\mathbf{a})=\alpha_{1}P_{1}(\mathbf{a})+\ldots+\alpha_{D}P_{D}(\mathbf{a}).$

In the case when $G$ is a finite field $\mathbb{F}_{p}$ for a prime $p$ and
$\mathcal{F}$ is a vector space of functions,
$\left\\{P_{1},\ldots,P_{D}\right\\}$ is a standard spanning set for
$\mathcal{F}$ in the linear algebraic sense. We extend this definition to the
case when $\mathcal{F}$ is defined over Abelian groups and say that
$\\{P_{1},\ldots,P_{D}\\}$ is a spanning set for $\mathcal{F}.$

######  Definition 6 (Local Correction Gadget).

Let $\mathcal{F}$ be a set of functions from $\\{0,1\\}^{n}$ to an Abelian
group $G$ with spanning set $\\{P_{1},\ldots,P_{D}\\}$. For any
$\mathbf{a}\in\\{0,1\\}^{n}$, an $(\varepsilon,q)$-correction gadget for
$\mathbf{a}$ is a distribution $\mathcal{D}$ over $(\\{0,1\\}^{n})^{q}$
satisfying the following two properties:

  1. 1.

There exists $c_{1},\ldots,c_{q}\in\mathbb{Z}$999We require that the
coefficients are $\mathbb{Z}$ because we are working with Abelian group, and a
rational number times a group element is not well defined. such that for any
$(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})\in\mathrm{supp}(\mathcal{D})$, the
following holds: for each element of the spanning set $P_{j}$ ($j\in[D]$).

$P_{j}(\mathbf{a})=c_{1}P_{j}(\mathbf{y}^{(1)})+\ldots+c_{q}P_{j}(\mathbf{y}^{(q)})$
(4)

  2. 2.

For any $i\in[q]$, the distribution of $\mathbf{y}^{(i)}$ is
$\varepsilon$-close to $U_{n}$.

The next claim shows that if we have an $(\varepsilon,q)$-correction gadget
for sufficiently small $\varepsilon$, that immediately gives us a
$(\delta,q)$-local correction algorithm for small enough $\delta$. We will use
the same notation in Definition 6.

######  Claim 3.3 (Correction gadget gives local correction algorithm).

If there is an $(\varepsilon,q)$-correction gadget for any
$\mathbf{a}\in\\{0,1\\}^{n}$ where $q(\delta+\varepsilon)<1/4$, then there is
a $(\delta,q)$-local correction algorithm for $\mathcal{F}$.

###### Proof of 3.3.

The existence of a correction gadget for each $\mathbf{a}\in\\{0,1\\}^{n}$
gives rise to a natural local correction algorithm for $\mathcal{F}.$ Given
access to a function $f:\\{0,1\\}^{n}\rightarrow G$ that is promised to be
$\delta$-close to some $P\in\mathcal{F}$ and an input
$\mathbf{a}\in\\{0,1\\}^{n}$, we sample
$(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})$ from the correction gadget
$\mathcal{D}$ for $\mathbf{a}$ and return

$c_{1}f(\mathbf{y}^{(1)})+\cdots+c_{q}f(\mathbf{y}^{(q)})$

where $c_{1},\ldots,c_{q}$ are the coefficients corresponding to the
correction gadget.

Since $P_{1},\ldots,P_{D}$ form a spanning set for $\mathcal{F}$, it follows
from Equation 4 and linearity that for any $P\in\mathcal{F}$ and any
$\mathbf{a}\in\\{0,1\\}^{n}$

$P(\mathbf{a})=c_{1}P(\mathbf{y}^{(1)})+\ldots+c_{q}P(\mathbf{y}^{(q)}).$

In particular, the correction algorithm outputs the correct answer
$P(\mathbf{a})$ as long as $f$ agrees with $P$ on each of
$\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)}$. We now upper bound the probability
of the correction algorithm outputting an incorrect value.

For any $i\in[q]$, the distribution of $\mathbf{y}^{(i)}$ is
$\varepsilon$-close to $U_{n}$. In other words, for any set
$T\subseteq\\{0,1\\}^{n}$,

$\displaystyle\left|\Pr_{(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})\sim\mathcal{D}}[\mathbf{y}^{(i)}\in
T]-\Pr_{\mathbf{y}^{(i)}\sim U_{n}}[\mathbf{y}^{(i)}\in
T]\right|\leq\varepsilon$

If $T$ is the set of points where $f$ and $P$ disagree, i.e.
$|T|/2^{n}\leq\delta$, then we have,

$\displaystyle\Pr_{(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})\sim\mathcal{D}}[f(\mathbf{y}^{(i)})\;\text{is
incorrect}]\leq\delta+\varepsilon$

Thus the probability that $f$ is incorrect on at least one of
$\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)}$, when
$(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})\sim\mathcal{D}$ is at most
$q(\delta+\varepsilon)<1/4$. ∎

In this subsection, we defined a local correction gadget, which is a
distribution with suitable properties. In 3.3, we showed that to construct a
local correction algorithm, it suffices to construct a local correction
gadget. In the following subsections, we will focus on constructing local
correction gadgets with, and then 3.3 would imply that we get a local
correction algorithm too.

####  3.1.2 Local Correction Algorithm for Linear Polynomials

We now prove Theorem 3.1. The main technical step in the proof is the
following lemma, which is to construct a local correction gadget for $1^{n}$.

######  Lemma 3.4 (Correction gadget for $1^{n}$).

Fix any odd positive integer $q$. For any $n$, there is a choice of
$c_{1},\ldots,c_{q}\in\mathbb{Z}$ and a distribution $\mathcal{D}$ over
$(\\{0,1\\}^{n})^{q}$ such that the following properties hold for
$c_{1},\ldots,c_{q}$ and any sample
$(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})$ from $\mathcal{D}$.

  * •

$c_{1}+\ldots+c_{q}=1$ and for all $i\in[n]$,

$\displaystyle c_{1}y^{(1)}_{i}+\ldots+c_{q}y^{(q)}_{i}=1$

  * •

For each $j\in[q]$, $\mathbf{y}^{(j)}$ is
$(1/2^{\Omega(q)}\cdot\sqrt{n})$-close to the $U_{n}$.

We first show how to prove Theorem 3.1 assuming this lemma. The idea is that
since the space of linear polynomials $\mathcal{P}_{1}$ is closed under
affine-shift, we can shift the query points to correct any point $\mathbf{a}$.
Lemma 3.4 is proved subsequently.

###### Proof of Theorem 3.1.

The space $\mathcal{P}_{1}$ of linear polynomials over $G$ has as a spanning
set the constant function $P_{0}(\mathbf{x})=1$ and the co-ordinate functions
$P_{j}(\mathbf{x})=x_{j}$ for each $j\in[n].$

From 3.3, it suffices to give a $(\varepsilon,q)$-correction gadget for any
$\mathbf{a}\in\\{0,1\\}^{n}$, where $\varepsilon=1/n$. Note that Lemma 3.4
directly yields a correction gadget $\mathcal{D}$ at the point $1^{n}$ for
$q=\mathcal{O}(\log n).$

To get a correction gadget at a point $\mathbf{a}\neq 1^{n}$, we simply shift
this correction gadget by $\mathbf{b}=1^{n}\oplus\mathbf{a}$ and use the fact
that the space of linear polynomials is preserved by such shifts.

More precisely, consider the distribution $\mathcal{D}_{\mathbf{b}}$ obtained
by sampling $(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})$ from $\mathcal{D}$
and shifting each element by $\mathbf{b}$ to get

$(\mathbf{z}^{(1)},\ldots,\mathbf{z}^{(q)})=(\mathbf{y}^{(1)}\oplus\mathbf{b},\ldots,\mathbf{y}^{(q)}\oplus\mathbf{b}).$

We retain the same coefficients $c_{1},\ldots,c_{q}$ as in Lemma 3.4.

To prove that $(\mathbf{z}^{(1)},\ldots,\mathbf{z}^{(q)})$ is an
$(\varepsilon,q)$-correction gadget for $\mathbf{a}$, it remains to verify

$\displaystyle c_{1}+\cdots+c_{q}$ $\displaystyle=1$ $\displaystyle
c_{1}z^{(1)}_{i}+\cdots+c_{q}z^{(q)}_{i}$ $\displaystyle=a_{i}\text{ for each
$i\in[n]$}$ (5)

The first of the above follows from Lemma 3.4. The second equality Equation 5
is also easily verified for $i$ such that $a_{i}=1$ since
$z^{(j)}_{i}=y^{(j)}_{i}$ in this case. For $i$ such that $a_{i}=0$, we see
that $z^{(j)}_{i}=1-y^{(j)}_{i}$ for each $j\in[q]$ and hence

$\sum_{j\in[q]}c_{j}z^{(j)}_{i}=\sum_{j\in[q]}c_{j}-\sum_{j\in[q]}c_{j}y^{(j)}_{i}=1-1=0=a_{i}.$

We have thus shown that Equation 5 holds for all $i\in[n]$. Further, since
$\mathbf{y}^{(j)}$ is $1/n$-close to uniform for each $j\in[q]$, so is
$\mathbf{z}^{(j)}.$ Overall, this implies that $\mathcal{D}_{\mathbf{b}}$ is a
correction gadget for $\mathbf{a}.$

3.3 then gives us the desired local correction algorithm. ∎

So now we have shown that constructing a local correction gadget for $1^{n}$
is sufficient to get a local correction gadget for any $\mathbf{a}$. In the
next subsection, we give a local correction gadget for $1^{n}$.

####  3.1.3 Correction Gadget for all 1s Vector

In this subsection, we prove Lemma 3.4. We first construct a Boolean matrix
with some interesting combinatorial and algebraic properties. The distribution
$\mathcal{D}$ in Lemma 3.4 is obtained later by sampling $n$ rows of this
matrix independently and uniformly at random.

The heart of our construction of a local correction gadget is the following
technical lemma. It shows that we can find a small number of nearly balanced
Boolean vectors, whose integer span contains the all 1s vector.

######  Lemma 3.5 (Construction of a matrix).

For any natural number $k$, there exists an integer matrix $A_{k}$ of
dimension $(2^{k}-1)\times(2k-1)$ with entries in $\\{0,1\\}$ and a vector
$\mathbf{c}\in\mathbb{Z}^{2k-1}$ such that $A_{k}\mathbf{c}=1^{2^{k}-1}$ and
there is exactly one row in $A_{k}$ that is $(1,\ldots,1)$. Additionally, for
any column of $A_{k}$, the Hamming weight of the column is in
$[2^{k-1}-1,2^{k-1}+1]$.

######  Remark 3.6.

The statement of this lemma is, in some sense, the best that can we hope for
as the lemma does not hold if each column is required to be _perfectly
balanced_. In fact, the above lemma does not hold even in the setting where
each column is required to have weight _exactly_ $w$ for some $w<2^{k}-1$: in
this case, $1^{2^{k}-1}$ would not even be in the $\mathbb{Q}$-linear span of
the columns of $A_{k}$.101010Consider a vector
$\mathbf{v}\in\mathbb{Q}^{2^{k}-1}$ the entries of which are $1-1/w$ or
$-1/w$, depending on whether the corresponding row in $A_{k}$ is the all $1$s
row or not. The vector $\mathbf{v}$ is orthogonal to the columns of $A_{k}$
but not the vector $1^{2^{k}-1}$.

Quantitatively, this lemma exhibits a near-tight converse to a lemma of Bafna,
Srinivasan, and Sudan [BSS20] who showed that for any $n\times k$ Boolean
matrix with an all-$1$s row, and columns that have Hamming weights in the
range $[n/2-\sqrt{n},n/2+\sqrt{n}]$ and also span the all $1$s column, we must
have $k=\tilde{\Omega}(\log n).$

###### Proof.

Fix a $k\in\mathbb{N}$. Given a non-negative integer $i<2^{k}$, we denote by
$\mathrm{bin}(i)$ the Boolean vector that denotes the $k$-bit binary expansion
of $i$ (with the first entry being the most significant bit).

##### Defining the base matrix

Let $M$ be a $(2^{k}-1)\times 2k$ matrix with entries in $\\{0,1\\}$. For all
$i\in[2^{k}-1]$ and $j\in[2k]$, let the $i^{th}$ row and the $j^{th}$ column
of $M$ be denoted by $\mathsf{row}^{(i)}$ and $\mathsf{col}^{(j)}$,
respectively. The $i^{th}$ row of $M$ is
$\mathsf{row}^{(i)}:=(\mathrm{bin}(i)\,\mathrm{bin}(i-1))$, i.e. in
$\mathsf{row}^{(i)}$, the first $k$ coordinates are $\mathrm{bin}(i)$ and the
next $k$ entries are $\mathrm{bin}(i-1)$, where for an integer $i$,
$\mathrm{bin}(i)$ denotes the binary representation of $i$.

$\displaystyle M=\begin{bmatrix}\vdots&\vdots\\\
\mathrm{bin}(i)&\mathrm{bin}(i-1)\\\
\vdots&\vdots\end{bmatrix}_{(2^{k}-1)\times 2k}$

Let $\mathbf{w}\in\mathbb{R}^{2k}$ be the following vector:

$\displaystyle\mathbf{w}=\left(2^{k-1},\ldots,2^{1},2^{0},\;-2^{k-1},\ldots,-2^{1},-2^{0}\right)$

It is easy to see that for any row $\mathsf{row}^{(i)}$ of $M$,
$\langle\mathsf{row}^{(i)},\mathbf{w}\rangle=i-(i-1)=1$. Thus,
$M\mathbf{w}=1^{2^{k}-1}$.

##### A useful observation

For any row $\mathsf{row}^{(i)}$, the $k^{th}$ and the $2k^{th}$ entry are
distinct, i.e. $\mathsf{row}^{(i)}_{k}\oplus\mathsf{row}^{(i)}_{2k}=1$, i.e.
$\mathsf{col}^{(k)}=1^{2^{k}-1}-\mathsf{col}^{(2k)}$.

##### Modifying the base matrix

Let $\tilde{M}$ be a $(2^{k}-1)\times 2k$ matrix and $\tilde{\mathbf{w}}$ be a
column vector of dimension $2k$. Let the $i^{th}$ row and the $j^{th}$ column
of $\tilde{M}$ be denoted by $\widetilde{\mathsf{row}}^{(i)}$ and
$\widetilde{\mathsf{col}}^{(j)}$, respectively. $\tilde{M}$ and
$\tilde{\mathbf{w}}$ are defined as follows:

$\displaystyle\widetilde{\mathsf{col}}^{(j)}=\begin{cases}1-\mathsf{col}^{(j)},&\text{if}\,j\neq
k\\\
\mathsf{col}^{(j)},&\text{if}\,j=k\end{cases}\quad\quad\tilde{w}_{j}=\begin{cases}w_{j},&\text{if}\,j\neq
k\\\ -w_{j},&\text{if}\,j=k\end{cases}$

It is easy to verify the following: for any $i\in[2^{k}-1]$,
$\langle\widetilde{\mathsf{row}}^{(i)},\tilde{\mathbf{w}}\rangle=-2$. Thus
$\tilde{M}(-\tilde{\mathbf{w}}/2)=1^{2^{k}-1}$.
Note that $\widetilde{\mathsf{col}}^{(k)}=\widetilde{\mathsf{col}}^{(2k)}$.
The first row of $M$, i.e.
$\mathsf{row}^{(1)}=(\mathrm{bin}(1)\mathrm{bin}(0))=(0,\ldots,0,1,0,\ldots,0)$.
The first row of $\tilde{M}$. i.e. $\widetilde{row}^{(1)}=(1,\ldots,1)$. Since
$\tilde{M}(-\tilde{\mathbf{w}}/2)=1^{2^{k}-1}$, this implies that
$\sum_{j=1}^{2k}(-\tilde{w}_{j}/2)=1$.

It’s also easy to verify that no row other than the first row of $\tilde{M}$
is $(1,1,\ldots,1).$

##### Integral coefficients

We have $-\tilde{w}_{k}/2=-\tilde{w}_{2k}/2=1/2$. Consider any row
$\widetilde{\mathsf{row}}^{(i)}$ of $\tilde{M}$. Since
$\widetilde{\mathsf{row}}^{(i)}_{k}=\widetilde{\mathsf{row}}^{(i)}_{2k}$, the
following equality holds:

$\widetilde{\mathsf{row}}^{(i)}_{k}(-\tilde{w}_{k}/2)\,+\,\widetilde{\mathsf{row}}^{(i)}_{2k}(-\tilde{w}_{2k}/2)\;=\;\widetilde{\mathsf{row}}^{(i)}_{k}\cdot
1\,+\,\widetilde{\mathsf{row}}^{(i)}_{2k}\cdot 0$ (6)

Let $\mathbf{c}\in\mathbb{Z}^{2k-1}$ be the following vector:
$c_{j}=(-\tilde{w}_{j}/2)$ if $j\neq k$, otherwise $c_{j}=1$. For any row
$\widetilde{\mathsf{row}}^{(i)}$, from Equation 6,
$\langle\widetilde{\mathsf{row}}^{(i)},\mathbf{c}\rangle=\langle\widetilde{\mathsf{row}}^{(i)},(-\tilde{\mathbf{w}}/2)\rangle=1$.
Let $A_{k}$ denote the matrix $\tilde{M}$ after removing the $2k^{th}$ column.
Then $A_{k}\mathbf{c}=1^{2^{k}-1}$.
Since $\sum_{j=1}^{2k}(-\tilde{w}_{j}/2)=1$, using Equation 6, we get that
$\sum_{j=1}^{2k-1}c_{j}=1$.

##### Columns are nearly balanced

Finally, we will prove that for each column $\widetilde{\mathsf{col}}^{(j)}$
of $A$, the Hamming weight of
$\widetilde{\mathsf{col}}^{(j)}\in[2^{k-1}-1,2^{k-1}+1]$. For any
$j\in[2k-1]$, the Hamming weight of $\mathsf{col}^{(j)}$ is in
$\left\\{2^{k-1}-1,2^{k-1}+1\right\\}$. This is because if $M$ had an
additional row $[\mathrm{bin}(0)\mathrm{bin}(2^{k}-1)]$, then each column of
$M$ would be exactly balanced, i.e. have Hamming weight of $2^{k-1}$. Then by
definition of $\widetilde{\mathsf{col}}^{(j)}$, it follows that Hamming weight
of each column of $A_{k}$ is also in $[2^{k-1}-1,2^{k-1}+1]$. ∎ Next, we are
going to describe a distribution $\mathcal{D}$ on $(\\{0,1\\}^{m})^{q}$, where
$m=2^{k}-1$ and $q=2k-1$. We will do this by randomly sampling rows of the
matrix $A_{k}$ given by Lemma 3.5. This will give us a local correction gadget
and finish the proof of Lemma 3.4.

###### Proof of Lemma 3.4.

Assume that $q=2k-1.$ To sample
$(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})\sim\mathcal{D}$ over
$(\\{0,1\\}^{n})^{q}$, we sample $n$ rows independenly and uniformly at random
from the rows of $A_{k}$ as constructed in Lemma 3.5 and define
$(y^{(1)}_{i},\ldots,y^{(q)}_{i})$ to be the $i$th sample for each $i\in[n].$

We now show that $\mathcal{D}$ has the required properties from the statement
of Lemma 3.4.

Let $(c_{1},\ldots,c_{q})=\mathbf{c}$ be as guaranteed by Lemma 3.5.

The first property holds from the properties of $A_{k}$ and $\mathbf{c}$. For
each $i\in[n]$, the vector $(y^{(1)}_{i},\ldots,y^{(q)}_{i})$ is a row of
$A_{k}$, and from Lemma 3.5, we know that the inner product of any row of
$A_{k}$ and $\mathbf{c}$ is $1$. Further, since $1^{q}$ is also a row of
$A_{k}$, it follows that the entries of $\mathbf{c}$ sum to $1$.

The second property follows from the fact that each column of $A_{k}$ has
relative Hamming weight in the range
$[\frac{1}{2}-2^{-k},\frac{1}{2}+2^{-k}]$. Thus, for any fixed $j\in[q]$ and
each $i\in[n]$, we have

$\mathop{\mathrm{Pr}}[y^{(j)}_{i}=1]\in\left[\frac{1}{2}-\frac{1}{2^{k}},\frac{1}{2}+\frac{1}{2^{k}}\right].$

Since for a fixed $j\in[q]$ the bits $\\{y^{(j)}_{i}\ |\ i\in[n]\\}$ are
mutually independent, we are now done by the following standard fact (which
can easily be proved by, say, following the proof of [Man11, Theorem 5.5,
Claim 5.6]).

######  Fact 3.7.

Let $\eta>0$. Let $\mathcal{D^{\prime}}$ be a distribution on $\\{0,1\\}^{n}$
such that for any $\mathbf{y}\sim\mathcal{D^{\prime}}$, the co-ordinates of
$\mathbf{y}$ are independent and for all $i\in[n]$,

$\displaystyle 1/2-\eta\leq\Pr[y_{i}=1]\leq 1/2+\eta.$

Then $\mathcal{D^{\prime}}$ is $\mathcal{O}(\eta\sqrt{n})$-close to $U_{n}$.

This concludes the proof of Lemma 3.4. ∎

Summarising the proof of Theorem 3.1 \- We first showed that it is enough to
focus on constructing local correction gadgets (see 3.3) and we can assume
without loss of generality that we want to decode at $1^{n}$. Then we
constructed a matrix with nice properties (see Lemma 3.5) and defined a
distribution for local correction gadget using this matrix.

###  3.2 Constant Error Algorithm via Error-Reduction

In this subsection, we explain the second step towards proving Theorem 1.1. We
show how to locally correct degree-$1$ polynomials in the regime of _constant_
error (one can think of this error to be around $1/1000$). We will do this by
reducing the problem to the case of low error (sub-constant error). The
results of this section also work for higher-degree polynomials.

We will show that there is a randomized algorithm $\mathcal{A}^{f}$ that given
oracle access to any function $f$ that is $\delta$-close to a degree-$d$
polynomial $P$ (think of $\delta$ as being a small enough constant depending
on $d$), has the following property: with high probability over the internal
randomness of $\mathcal{A}^{f}$, the function computed by $\mathcal{A}^{f}$ is
$\eta$-close to $P$, where $\eta<\delta$. We state it formally below.

######  Lemma 3.8 (Error reduction for constant error).

Fix any Abelian group $G$ and a positive integer $d$. The following holds for
$\delta<1/2^{\mathcal{O}(d)}$ and $K=2^{\mathcal{O}(d)}$ where the
$\mathcal{O}(\cdot)$ hides a large enough absolute constant.
For any $\eta,\delta$, where $\eta<\delta$, there exists a randomized
algorithm $\mathcal{A}$ with the following properties: Let $f:\\{0,1\\}^{n}\to
G$ be a function and let $P:\\{0,1\\}^{n}\to G$ be a degree-$d$ polynomial
such that $\delta(f,P)\leq\delta$, and let $\mathcal{A}^{f}$ denotes that
$\mathcal{A}$ has oracle access to $f$, then

$\displaystyle\Pr[\delta(\mathcal{A}^{f},P)>\eta]<1/10,$

where the above probability is over the internal randomness of
$\mathcal{A}^{f}$. Further, for every $\mathbf{x}\in\\{0,1\\}^{n}$,
$\mathcal{A}^{f}$ makes $K^{T}$ queries to $f$ and
$T=\mathcal{O}\left(\log\left(\dfrac{\log(1/\eta)}{\log(1/\delta)}\right)\right)$.

Putting this together with Theorem 3.1, we immediately get the following
algorithmic result, which is the main result of this subsection.

######  Theorem 3.9 (Unique local correction algorithm for constant error).

Fix any Abelian group $G$. The space $\mathcal{P}_{1}$ of degree-$1$
polynomials has a $(\delta,q)$-local correction algorithm where $\delta>0$ is
a small enough absolute constant and $q=\mathcal{O}(\log
n\cdot\mathop{\mathrm{poly}}(\log\log n)).$

###### Proof.

Given oracle access to a function $f$ that is $\delta$-close to a degree-$1$
polynomial $P$, Lemma 3.8 (with $\eta=o(1/\log n)$) shows how to get access to
a randomized oracle $\mathcal{A}^{f}$ that makes
$\mathop{\mathrm{poly}}(\log\log n)$ queries to $f$ is $\eta$-close to $P$
except with small probability. We apply the local correction algorithm from
Theorem 3.1 with oracle access to $\mathcal{A}^{f}$, repeating a constant
number of times to reduce the error down to $1/10.$ The latter algorithm works
for every choice of the internal randomness of $\mathcal{A}^{f}$ such that
$\mathcal{A}^{f}$ and $P$ are $\eta$-close. This gives us an overall error
probability of

$\Pr[\delta(\mathcal{A}^{f},P)>\eta]+1/10\leq 1/10+1/10<1/4,$

as desired. The query complexity of this algorithm is the product of the query
complexities of $\mathcal{A}^{f}$ and the algorithm from Theorem 3.1. ∎

In the rest of this subsection, we will prove Lemma 3.8. The algorithm
$\mathcal{A}^{f}$ in Lemma 3.8 will be a recursive algorithm. Each recursive
iteration of the algorithm $\mathcal{A}^{f}$ uses the same ‘base algorithm’
$\mathcal{B}$, which will be the core of our error reduction algorithm from
small constant error. In the next lemma, we formally state the properties of
the base algorithm.

######  Lemma 3.10 (Base Error Reduction Algorithm).

Fix any Abelian group $G$ and a positive integer $d$. The following holds for
$K=2^{O(d)}$. For any $0<\gamma<1$, there exists a randomized algorithm
$\mathcal{B}$ with the following properties: Let $g:\\{0,1\\}^{n}\to G$ be a
function and let $P:\\{0,1\\}^{n}\to G$ be a degree-$d$ polynomial such that
$\delta(g,P)\leq\gamma$, and let $\mathcal{B}^{g}$ denotes that $\mathcal{B}$
has oracle access to $g$, then

$\displaystyle\mathbb{E}[\delta(\mathcal{B}^{g},P)]<O(K^{2})\cdot\gamma^{1.5}$

where the above expectation is over the internal randomness of $\mathcal{B}$.
Further, for every $\mathbf{x}\in\\{0,1\\}^{n}$, $\mathcal{A}^{g}$ makes $K$
queries to $g$.

We defer the construction of the base algorithm and proof of Lemma 3.10 to the
next subsection, Section 3.2.1. For now, we assume Lemma 3.10 and proceed to
describe the recursive construction of $\mathcal{A}^{f}$ and prove Lemma 3.8.

###### Proof of Lemma 3.8.

Let $\mathcal{B}$ be the algorithm given by Lemma 3.10. We define a sequence
of algorithms $\mathcal{A}_{0}^{f},\mathcal{A}_{1}^{f},\ldots,$ as follows.

The algorithm $\mathcal{A}^{f}_{t}$ computes a function mapping inputs in
$\\{0,1\\}^{n}$ along with a uniformly random string from $\\{0,1\\}^{r_{t}}$
to a random group element in $G$ ($t$ denotes the number of recursive calls).
• $\mathcal{A}_{0}^{f}$ just computes the function $f.$ (In particular,
$r_{0}=0$.) • For each $t>0,$ we inductively define $r_{t}=r_{t-1}+r$, where
$r$ is the amount of randomness required by the base error reduction algorithm
$\mathcal{B}$.
On input $\mathbf{x}$ and random string $\sigma_{t}\sim U_{r_{t}}$, the
algorithm $\mathcal{A}_{t}^{f}$ algorithm runs the algorithm $\mathcal{B}$ on
$\mathbf{x}$ using the first $r$ bits of $\sigma_{t}$ as its source of
randomness, and with oracle access to $\mathcal{A}_{t-1}^{f}$ using the
remaining $r_{t-1}$ bits of $\sigma_{t}$ as randomness.
The algorithm $\mathcal{A}^{f}$ will be $\mathcal{A}_{T}^{f}$ for
$T=C\cdot\log\left(\dfrac{\log(1/\eta)}{\log(1/\delta)}\right)$ where $C$ is a
large enough absolute constant chosen below.

Query complexity: An easy inductive argument shows that $\mathcal{A}^{f}$
makes at most $K^{T}$ queries to $f.$

Error probability: We now analyze the error made by the above algorithms. We
will argue inductively that for each $t\leq T$ and
$\delta_{t}:=\delta^{(1.1)^{t}}$, we have

$\Pr_{\sigma_{t}}[\,\underbrace{\delta(\mathcal{A}^{f}_{t}(\cdot,\sigma_{t}),P)>\delta_{t}\,}_{:=\,\mathcal{E}_{t}}]\;\leq\;\sum_{j=1}^{t}\frac{1}{100^{j}}\;<\;\frac{1}{10}.$
(7)

In the inductive proof, we will need that $\delta_{0}=\delta<2^{-C_{1}\cdot
d}$ for a large enough absolute constant $C_{1}.$

We now proceed with the induction. The base case ($t=0$) is trivial as
$\delta(\mathcal{A}^{f}_{t},P)=\delta_{0}$ by definition.

Now assume that $t>1$. We decompose the random string $\sigma_{t}$ into its
first $r$ bits, denoted $\sigma$, and its last $r_{t-1}$ bits, denoted
$\sigma_{t-1}.$ We bound the probability in Equation 7 as follows. (Note that
the event $\mathcal{E}_{t-1}$ below only depends on $\sigma_{t-1}.$)

$\Pr_{\sigma_{t}}[\mathcal{E}_{t}]\,\leq\,\Pr_{\sigma_{t-1}}[\mathcal{E}_{t-1}]+\Pr_{\sigma_{t}}[\mathcal{E}_{t}\
|\
\neg\mathcal{E}_{t-1}]\,\leq\,\sum_{j=1}^{t-1}\frac{1}{100^{j}}+\Pr_{\sigma_{t}}[\mathcal{E}_{t}\
|\ \neg\mathcal{E}_{t-1}]$ (8)

where we used the induction hypothesis for the second inequality. To bound
$\Pr_{\sigma_{t}}[\mathcal{E}_{t}\ |\ \neg\mathcal{E}_{t-1}]$, fix any choice
of $\sigma_{t-1}$ so that $\neg\mathcal{E}_{t-1}$ holds, i.e. so that
$\delta(\mathcal{A}^{f}_{t-1},P)\leq\delta_{t-1}$. By the guarantee on
$\mathcal{B}$, i.e. Lemma 3.10, we know that

$\mathbb{E}_{\sigma}[\delta(\mathcal{A}^{f}_{t}(\cdot,\sigma_{t}),P)]<\mathcal{O}(K^{2})\cdot\gamma^{1.5},$

where $\gamma=\delta(\mathcal{A}^{f}_{t-1}(\cdot,\sigma_{t-1}),P)$.
Substituting it above, we get,

$\displaystyle\mathbb{E}_{\sigma}[\delta(\mathcal{A}^{f}_{t}(\cdot,\sigma_{t}),P)]\,\leq\,\mathcal{O}(K^{2})\cdot\delta_{t-1}^{1.5}\,\leq\,\delta_{t-1}^{1.25}$

where for the final inequality, we use the fact that

$\mathcal{O}(K^{2})\cdot\delta_{t-1}^{0.25}\leq\mathcal{O}(K^{2})\cdot\delta_{0}^{0.25}\leq
1$

as long as $\delta_{0}=\delta\leq 2^{-C_{1}d}$ for a large enough constant
$C_{1}.$ Continuing the above computation, we see that by Markov’s inequality

$\Pr_{\sigma}[\mathcal{E}_{t}]\,\leq\,\frac{\delta_{t-1}^{1.25}}{\delta_{t}}\;=\;\delta^{\Omega((1.1)^{t})}\,\leq\,\frac{1}{100^{t}}$

where the final inequality holds for all $t$ as long as $\delta\leq
2^{-C_{1}d}$ for a large enough constant $C_{1}.$ Since this inequality holds
for any choice of $\sigma_{t-1}$ so that $\neg\mathcal{E}_{t-1}$ holds, we can
plug this bound into Equation 8 to finish the inductive case of Equation 7.

Setting $T=C\cdot\log\left(\dfrac{\log(1/\eta)}{\log(1/\delta)}\right)$ for a
large enough constant $C$, we see that $\delta_{T}<\eta.$ In this case,
Equation 7 implies the required bound on the error probability of
$\mathcal{A}^{f}.$ ∎

Thus we have shown so far that given the base algorithm $\mathcal{B}$, we do
get an error reduction algorithm from small constant error to error
$\mathcal{O}(1/\log n)$. Now it remains to describe the base error reduction
algorithm. In the next subsection, we describe the base algorithm
$\mathcal{B}$ and prove Lemma 3.10.

####  3.2.1 The Base Algorithm and its Analysis

In this section, we prove Lemma 3.10, which will then complete the proof of
the error reduction algorithm from small constant to sub-constant error (see
Lemma 3.8). Before we describe $\mathcal{B}$, we will define an error
reduction gadget, which is a variant of the local correction gadget defined
previously (Definition 6).

######  Definition 7 (Error-reduction Gadget for $\mathcal{P}_{d}$).

For $\rho\in(0,1)$, an $(\rho,q)$-error reduction gadget for $\mathcal{P}_{d}$
is a distribution $\mathcal{D}$ over $(\\{0,1\\}^{n})^{q}$ satisfying the
following two properties:

  1. 1.

There exists $c_{1},\ldots,c_{q}\in\mathbb{Z}$ such that for any
$(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})\in\mathrm{supp}(\mathcal{D})$, the
following holds true for each $P\in\mathcal{P}_{d}$ and each
$\mathbf{a}\in\\{0,1\\}^{n}$

$P(\mathbf{a})=c_{1}P(\mathbf{a}\oplus\mathbf{y}^{(1)})+\ldots+c_{q}P(\mathbf{a}\oplus\mathbf{y}^{(q)}).$
(9)

  2. 2.

For any $i\in[q]$, the bits of $\mathbf{y}^{(i)}$ are i.i.d. Bernoulli random
variables that are $\rho$-close to uniform. Equivalently, each co-ordinate is
$1$ with probability $p_{i}\in[\frac{1-\rho}{2},\frac{1+\rho}{2}].$

To describe the base algorithm $\mathcal{B}$ and prove Lemma 3.10, we need an
error-reduction gadget for $\mathcal{P}_{d}$, the space of degree-$d$
polynomials over a group $G.$ The next lemma says that there exists an error-
reduction gadget for $\mathcal{P}_{d}$, with small number of queries for
constant $d$ and $\rho$.

######  Lemma 3.11 (Constructing an error-reduction gadget for
$\mathcal{P}_{d}$).

Fix any Abelian group $G$ and any $\rho>0.$ Then $\mathcal{P}_{d}$ has a
$(\rho,q)$-error-reduction gadget where $q=2^{O(d/\rho)}.$

Assuming the existence of error-reduction gagdet through the above lemma, we
first finish the proof of Lemma 3.10. We prove Lemma 3.11 subsequently.

The idea is as follows. In base algorithm, we use the error-reduction gadget
to correct the polynomial at a _random point_ $\mathbf{a}\in\\{0,1\\}^{n}$.
This process is likely to give the right answer except with probability
$q\gamma$ since, after shifting, each query is now _uniformly_ distributed,
and hence the chance that any of the queried points is an error point of $g$
is at most $\gamma$. We reduce the error by repeating this process three times
and taking a majority vote. To analyze this algorithm, we need to understand
the probability that two iterations of this process both evaluate $g$ at an
error point. We do this using hypercontractivity (more specifically Theorem
2.3).

###### Proof of Lemma 3.10.

Let $\mathcal{D}$ be a $(1/10,q)$-error-reduction gadget as given by Lemma
3.11. The algorithm $\mathcal{B}$, given oracle access to
$g:\\{0,1\\}^{n}\rightarrow G$ and $\mathbf{a}\in\\{0,1\\}^{n}$, does the
following.

  * •

Repeat the following three times independently. Sample
$(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})$ from $\mathcal{D}$ and compute

$c_{1}g(\mathbf{a}\oplus\mathbf{y}^{(1)})+\cdots+c_{q}g(\mathbf{a}\oplus\mathbf{y}^{(q)})$

where $c_{1},\ldots,c_{q}$ are the coefficients corresponding to the error-
reduction gadget.

  * •

Output the plurality among the three group elements $b_{1},b_{2},b_{3}$
computed above.

The number of queries made by the algorithm is $K=O(q)=2^{O(d)}$ as claimed.
So it only remains to analyze $\delta(\mathcal{B}^{g},P)$. From now on, let
$\mathbf{a}$ be a uniformly random input in $\\{0,1\\}^{n}.$

For $i\in\\{1,2,3\\},$ let $\mathcal{E}_{i}$ denote the event that $b_{i}\neq
P(\mathbf{a}).$ We have

$\operatorname*{\mathbb{E}}[\delta(\mathcal{B}^{g},P)]\;=\;\Pr[\mathcal{B}^{g}(\mathbf{a})\neq
g(\mathbf{a})]\;\leq\;\Pr[\mathcal{E}_{1}\wedge\mathcal{E}_{2}]\,+\,\Pr[\mathcal{E}_{2}\wedge\mathcal{E}_{3}]\,+\,\Pr[\mathcal{E}_{1}\wedge\mathcal{E}_{3}],$

where the above probability is over the randomness of $\mathcal{B}$. It
therefore suffices to show that each of the three terms in the final
expression above is at most $O(q^{2})\cdot\gamma^{1.5}.$

Without loss of generality, consider the event
$\mathcal{E}_{1}\wedge\mathcal{E}_{2}$. Let
$(\mathbf{y}^{(1)},\ldots,\mathbf{y}^{(q)})$ and
$(\mathbf{z}^{(1)},\ldots,\mathbf{z}^{(q)})$ be the two independent samples
from $\mathcal{D}$ in the two corresponding iterations.

Let $T$ denote the set of points where $g$ and $P$ disagree. It follows from
Equation 9 that the algorithm correctly computes $P(\mathbf{a})$ in the first
iteration as long as none of the queried points lie in the set $T$. A similar
statement also holds for the second iteration. This reasoning implies that

$\Pr[\mathcal{E}_{1}\wedge\mathcal{E}_{2}]\leq\sum_{i,j=1}^{q}\Pr[\underbrace{\mathbf{a}\oplus\mathbf{y}^{(i)}}_{\mathbf{u}^{(i)}}\in
T\;\wedge\;\underbrace{\mathbf{a}\oplus\mathbf{z}^{(j)}}_{\mathbf{v}^{(j)}}\in
T].$ (10)

We bound each term in the above sum using hypercontractivity, Theorem 2.3.

Fix $i,j\in[q]$. Note that for every fixing of $\mathbf{y}^{(i)}$, the vector
$\mathbf{u}^{(i)}$ is distributed uniformly over $\\{0,1\\}^{n}$ (because
$\mathbf{a}$ is uniform over $\\{0,1\\}^{n}$). In particular, this implies the
following:

  * •

The random variable $\mathbf{u}^{(i)}$ is uniformly distributed.

  * •

The random variables $\mathbf{u}^{(i)}$ and $\mathbf{y}^{(i)}$ are
independent.

This means that $\mathbf{v}^{(j)}$ which is equal to
$(\mathbf{u}^{(i)}\,\oplus\,\mathbf{y}^{(i)})\,\oplus\,\mathbf{z}^{(j)}$ is
drawn from the noise distribution $\mathcal{N}_{\rho}(\mathbf{u}^{(i)})$.
Further, the parameter $\rho\leq 1/100$ since the co-ordinates of
$\mathbf{y}^{(i)}$ and $\mathbf{z}^{(j)}$ are i.i.d. Bernoulli random
variables that are each $1/10$-close to uniform.

Using Theorem 2.3, we have

$\mathop{\mathrm{Pr}}[\mathbf{u}^{(i)}\in T\wedge\mathbf{v}^{(j)}\in
T]\leq\gamma^{2/1+|\rho|}\leq\gamma^{1.5}.$

Plugging this into Equation 10 implies that
$\Pr[\mathcal{E}_{1}\wedge\mathcal{E}_{2}]\leq\mathcal{O}(q^{2})\cdot\gamma^{1.5}$
(union bound over all pairs $(i,j)\in[q]\times[q]$). Therefore,
$\Pr[\mathcal{B}^{g}(\mathbf{a})\neq
g(\mathbf{a})]\leq\mathcal{O}(q^{2})\cdot\gamma^{1.5}$ and this concludes the
analysis of $\mathcal{B}.$ ∎

So far we have shown that if we have an error-reduction gadget, then we can
use it to construct a base algorithm $\mathcal{B}$, which in turn can be used
recursively to construct an error-reduction algorithm for small constant error
to sub-constant error. We now show how to construct the error-reduction gadget
and prove Lemma 3.11. This requires the following standard claim (implied e.g.
by Möbius inversion) that shows that any degree-$d$ polynomial over
$\\{0,1\\}^{n}$ (even with group coefficients) can be interpolated from its
values on a Hamming ball of radius $d.$ For completeness, we give a short
proof.

######  Lemma 3.12.

Fix $d\in\mathbb{N}$. For any natural number $m\geq d$ and any Hamming ball
$B$ of radius $d$,

$P(0^{m})=\sum_{\mathbf{b}\in B}\alpha_{\mathbf{b}}P(\mathbf{b})$

where the $\alpha_{\mathbf{b}}$ are integer coefficients.

###### Proof.

Assume that

$P(\mathbf{x})=\sum_{I\subseteq[n]:|I|\leq d}c_{I}\prod_{i\in I}x_{i}.$

By Möbius inversion (see item 1 of Theorem 2.1), we know that

$c_{I}=\sum_{J\subseteq I}(-1)^{|I\setminus J|}P(1_{J})$

where $1_{J}\in\\{0,1\\}^{m}$ denotes the indicator vector of set $J.$ Putting
the above equalities together gives us

$P(\mathbf{x})=\sum_{|\mathbf{b}|\leq
d}\alpha_{\mathbf{b},\mathbf{x}}^{\prime}P(\mathbf{b})$

for suitable integer coefficients $\alpha^{\prime}_{\mathbf{b},\mathbf{x}}.$

Now, assume $B$ is the Hamming ball of radius $d$ around the point
$\mathbf{c}\in\\{0,1\\}^{m}$. Replacing $\mathbf{x}$ by
$\mathbf{x}\oplus\mathbf{c}$ in $P$ does not increase the degree of the
polynomial (since this only involves negating a subset of the variables).
Applying this substitution above yields

$P(\mathbf{x}\oplus\mathbf{c})=\sum_{|\mathbf{b}|\leq
d}\alpha_{\mathbf{b},\mathbf{x}}^{\prime}P(\mathbf{b}\oplus\mathbf{c})=\sum_{\mathbf{b}\in
B}\alpha_{\mathbf{b},\mathbf{x}}P(\mathbf{b}).$

Setting $\mathbf{x}=\mathbf{c}$ yields the statement of the lemma. ∎

We end this section by completing the proof of Lemma 3.11.

###### Proof of Lemma 3.11.

The idea is to apply Lemma 3.12 on a random subcube, as defined in Definition
5.

More precisely, for an even integer $k>2d$ that we will fix below, let
$\mathbf{a}\in\\{0,1\\}^{n}$ be arbitrary and let $h:[n]\rightarrow[k]$ be
chosen uniformly at random. Let $C=C_{\mathbf{a},h}$ be the corresponding
subcube of $\\{0,1\\}^{n}$. Let $Q(y_{1},\ldots,y_{k})$ denote $P|_{C}$, the
restriction of $P$ to this subcube.

Fix a Hamming ball $B$ of radius $d$ in $\\{0,1\\}^{k}$ centred at a point
$\mathbf{c}$ of weight exactly $k/2.$

Since $Q$ is a polynomial of degree at most $d$, applying Lemma 3.12 to $Q$
and the ball $B$ yields an equality

$Q(0^{k})=\sum_{\mathbf{b}\in\mathbf{B}}\alpha_{\mathbf{b}}Q(\mathbf{b}).$

Since $Q$ is a restriction of $P$, the above equality can be rephrased in
terms of $P$ as

$P(x(0^{k}))=\sum_{\mathbf{b}\in\mathbf{B}}\alpha_{\mathbf{b}}P(x(\mathbf{b})).$

From the definition of the cube $C$, it follows that $x(0^{k})=\mathbf{a}$ and
thus the above gives us an equality of the type desired in an error-reduction
gadget (Equation 9). To finish the proof, we only need to argue that each
$x(\mathbf{b})$ has the required distribution.

Note that for each $\mathbf{b}\in B$, we have

$x(\mathbf{b})=\mathbf{a}\oplus\mathbf{b}_{h}$

where $\mathbf{b}_{h}$ is the random vector in $\\{0,1\\}^{n}$ that at co-
ordinate $i$ takes the random value $b_{h(i)}$. Since $h$ is chosen uniformly
at random, it follows that the entries of $\mathbf{b}_{h}$ are independent and
the $i$th co-ordinate is a Bernoulli random variable that takes the value $1$
with probability equal to the relative Hamming weight of $\mathbf{b}.$

To conclude the argument, note that $\mathbf{b}$ is at Hamming distance at
most $d$ from $\mathbf{c}$, implying that it has relative Hamming weight in
the range

$\left[\frac{1}{2}-\frac{2d}{k},\frac{1}{2}+\frac{2d}{k}\right].$

Setting $k$ larger than $4d/\rho$ gives us the desired value for the parameter
of the Bernoulli distribution.

Finally, the number of queries $q$ made by the error-reduction gadget is
dictated by the size of a Hamming ball in $k=O(d/\rho)$ dimensions. Since this
is at most $2^{k}$, it follows that we have a $(\rho,2^{O(d/\rho)})$-error-
reduction gadget. ∎

Summarising the proof of Lemma 3.8 \- We first show that given a base
algorithm $\mathcal{B}$ (see Lemma 3.10), we can use it recursively to
construct an error reduction algorithm (see the algorithm in the proof of
Lemma 3.8). Then we show that using an error-reduction gadget, we can design a
base algorithm $\mathcal{B}$, where we use hypercontractivity to bound the
error of the base algorithm. Finally, we use Möbius inversion (see Lemma 3.12)
to construct an error-reduction gadget.

###  3.3 Error Close to Half the Minimum Distance (Proof of Theorem 1.1)

In this subsection, we explain the third step towards proving Theorem 1.1. We
will show that there is a randomized algorithm $\mathcal{A}^{f}$ that given
oracle access to any function $f$ that is $\delta$-close to a low-degree
polynomial $P$ (think of $\delta$ to be very close to half the minimum
distance, i.e. $1/2^{d+1}-\varepsilon$ for degree $d$ polynomials), has the
following property: with high probability over the internal randomness of
$\mathcal{A}$, $\mathcal{A}^{f}$ is $\eta$-close to $P$, where $\eta<\delta$.
We state it formally below.

######  Lemma 3.13.

Fix any Abelian group $G$ and a positive integer $d$. For any $\eta,\delta$,
where $\eta<\delta$ and $\delta<1/2^{d+1}-\varepsilon$ for $\varepsilon>0$,
there exists a randomized algorithm $\mathcal{A}$ with the following
properties:
Let $f:\\{0,1\\}^{n}\to G$ be a function and let $P:\\{0,1\\}^{n}\to G$ be a
degree $d$ polynomial such that $\delta(f,P)\leq\delta$, and let
$\mathcal{A}^{f}$ denotes that $\mathcal{A}$ has oracle access to $f$, then

$\displaystyle\Pr[\delta(\mathcal{A}^{f},P)>\eta]<1/10,$

where the above probability is over the internal randomness of $\mathcal{A}$,
and for every $\mathbf{x}\in\\{0,1\\}^{n}$, $\mathcal{A}^{f}$ makes $2^{k}$
queries to $f$, where
$k=\mathop{\mathrm{poly}}(\frac{1}{\varepsilon},\frac{1}{\eta})$.

Putting this together with the unique correction algorithm for constant error
(Theorem 3.9), we immediately get Theorem 1.1. Since the details are almost
identical to the proof of Theorem 3.9, we omit the proof.

Now we state the algorithm $\mathcal{A}^{f}$.

1 Input: $f$ and $\mathbf{a}\in\\{0,1\\}^{n}$ 2 3Choose
$k=1/(\varepsilon^{5}\eta^{3})$ Sample a uniformly random $h:[n]\to[k]$ // $h$
is the internal randomness of $\mathcal{A}^{f}$ 4 Construct the cube
$\mathsf{C}:=C_{\mathbf{a},h}$ according to Definition 5 Let
$\tilde{f}:=f|_{\mathsf{C}}$ // $f|_{\mathsf{C}}$ is the restriction of $f$ to
the subcube $\mathsf{C}$ Query $\tilde{f}$ on all inputs in $\\{0,1\\}^{k}$
and use the algoritm from Theorem A.1 to find the polynomial $\tilde{P}$ on
$\mathsf{C}$ such that $\delta(\tilde{f},\tilde{P})<1/2^{d+1}$ // $2^{k}$
queries to $f$ 5 if  _such a polynomial $\tilde{P}$ is found_ then return
_$\tilde{P}(0^{k})$_ // $x(0^{k})=\mathbf{a}$ 6 7else return _0_ // An
arbitrary value 8 9 Algorithm 1 Error Reduction Algorithm $\mathcal{A}^{f}$

We now analyze Algorithm 1 and prove Lemma 3.13.

###### Proof of Lemma 3.13.

Let $P$ be the degree $d$ polynomial such that $\delta(f,P)\leq 1/2^{d+1}$.
The degree of $P$ is at most $d$ when $P$ is restricted to
$\mathsf{C}=C_{\mathbf{a},h}$. If
$\delta(P|_{\mathsf{C}},\tilde{f})<1/2^{d+1}$, then
$\tilde{P}=P|_{\mathsf{C}}$. In particular,
$\tilde{P}(x(0^{k}))=P(\mathbf{a})$, i.e. the output of the algorithm is
correct.

Equivalently, $\mathcal{A}^{f}(\mathbf{a})=P(\mathbf{a})$ unless
$\delta(P|_{\mathsf{C}},\tilde{f})\geq 1/2^{d+1}$. In the next lemma, we will
show that with high probability over random $\mathbf{a}$ and $h$,
$\delta((P|_{\mathsf{C}},\tilde{f})<1/2^{d+1}.$

######  Lemma 3.14.

Sample $\mathbf{a}$ and $h$ uniformly at random, and let
$\mathsf{C}=C_{\mathbf{a},h}$ be the subcube of dimension $k$ as described in
Definition 5. Then,

$\displaystyle\Pr_{\mathbf{a},h}[\delta(P|_{\mathsf{C}},\tilde{f})\geq
1/2^{d+1}]<\eta/10$

We prove Lemma 3.14 below. For now, let us assume Lemma 3.14 and finish the
proof of Lemma 3.13. We have,

$\displaystyle\Pr_{\mathbf{a},h}[\delta(P|_{\mathsf{C}},\tilde{f})\geq
1/2^{d+1}]<\eta/10$
$\displaystyle\Rightarrow\mathbb{E}_{h}\,\Pr_{\mathbf{a}}[\delta(P|_{\mathsf{C}},\tilde{f})\geq
1/2^{d+1}]<\eta/10$

Note that if we fix $h$, i.e. the internal randomness of $\mathcal{A}^{f}$,
then $\delta(\mathcal{A}^{f},f)$ is at most
$\Pr_{\mathbf{a}}[\delta(P|_{\mathsf{C}},\tilde{f})\geq 1/2^{d+1}]$, as the
algorithm always outputs $P(\mathbf{a})$ correctly when
$\delta(P|_{\mathsf{C}},\tilde{f})<1/2^{d+1}$ . Then from the above
inequality, we have,

$\displaystyle\mathbb{E}_{h}\,[\delta(\mathcal{A}^{f},f)]<\eta/10$
$\displaystyle\Rightarrow\Pr_{h}[\delta(\mathcal{A}^{f},f)>\eta]\leq 1/10$
(Markov’s Inequality)

As commented in Algorithm 1, for each $\mathbf{a}\in\\{0,1\\}^{n}$,
$\mathcal{A}^{f}$ makes $2^{k}$ queries to $f$. ∎

Now we give the proof of Lemma 3.14.

###### Proof of Lemma 3.14.

Let $E$ denote the subset of points in $\\{0,1\\}^{n}$ where $P$ and $f$
disagree, i.e.
$E:=\left\\{\mathbf{x}\in\\{0,1\\}^{k}\;\middle|\;f(\mathbf{x})\neq
P(\mathbf{x})\right\\}$. We know that $|E|/2^{n}\leq 1/2^{d+1}-\varepsilon$.
Applying Lemma 2.4, we get that for $k=\frac{1}{\varepsilon^{5}\eta^{3}}$ (we
assume without loss of generality that $\varepsilon,\eta$ are small enough for
$k$ to satisfy the hypothesis of Lemma 2.4)

$\displaystyle\Pr\Pr_{\mathbf{a},h}[\delta(P|_{\mathsf{C}},\tilde{f})\geq
1/2^{d+1}]<\eta/10,$

and this completes the proof of Lemma 3.14. ∎

##  4 Combinatorial Bound for List Decoding Linear Polynomials

In this section, we are going to prove Theorem 1.2. Let $G$ be any Abelian
group and let $f:\\{0,1\\}^{n}\to G$ be a polynomial such that $f$ is
$(1/2-\varepsilon)$-close to $\mathcal{P}_{1}$. For small enough
$\varepsilon$, $(1/2-\varepsilon)$ is strictly more than the unique decoding
radius of $\mathcal{P}_{1}$, which means that there can be several polynomials
in $\mathcal{P}_{1}$ that are $(1/2-\varepsilon)$-close to $f$. We denote the
set of these polynomials by $\mathsf{List}_{\varepsilon}^{f}$, defined as
follows:

$\displaystyle\mathsf{List}_{\varepsilon}^{f}:=\left\\{P(\mathbf{x})\in\mathcal{P}_{1}\;\middle|\;\delta(f,P)\leq
1/2-\varepsilon\right\\}$

Let $L(\varepsilon)=|\mathsf{List}_{\varepsilon}^{f}|$. In Theorem 1.2 we show
that $\mathsf{List}_{\varepsilon}^{f}$ is a _small_ list, i.e.
$L(\varepsilon)=\mathop{\mathrm{poly}}(1/\varepsilon)$. We prove Theorem 1.2
in the following steps:

  * •

Step 1: We prove that the list size is always a finite number, even though the
underlying group $G$ is not finite (see 4.1).

  * •

Step 2: We show that to give an upper bound on $L(\varepsilon)$, we can assume
without loss of generality the underlying group is finite (see 4.2).

  * •

Step 3: We decompose the group $G$ in two cases, depending on the order of the
elements in $G$:

    * –

Case 1: Every element has order a power of $q$ for a prime
$q\in\left\\{2,3\right\\}$ (see Theorem 4.3).

    * –

Case 2: Every element has order a power of $p$ for a prime $p\geq 5$ (see
Theorem 4.4).

We start by describing the first two steps.

If $G$ is not finite, e.g. $G=\mathbb{R}$, then apriori it is not clear
whether $L(\varepsilon)$ is even finite or not. As a warm-up, we first prove
that $L(\varepsilon)$ is finite. This result will also be used later in our
proofs.

######  Claim 4.1 (The list is finite).

Let $f:\\{0,1\\}^{N}\to G$ be a polynomial which is $(1/2-\varepsilon)$-close
to $\mathcal{P}_{1}$, for $\varepsilon>0$. Then,
$|\mathsf{List}_{\varepsilon}^{f}|\leq 2^{2^{N}}$.

###### Proof.

For every $P\in\mathsf{List}_{\varepsilon}^{f}$, there is a subset of size at
least $(1/2+\varepsilon)\cdot 2^{N}$ on which $P$ and $f$ agree. Two distinct
polynomials in $\mathsf{List}_{\varepsilon}$ cannot agree on more than
$1/2\cdot 2^{N}$ points (as $\delta(\mathcal{P}_{1})\geq 1/2$). Thus for every
subset of size at least $(1/2+\varepsilon)\cdot 2^{N}$, there exists at most
one polynomial $P$ in $\mathsf{List}_{\varepsilon}^{f}$ such that $f$ and $P$
agree on that subset. Hence the number of polynomials in
$\mathsf{List}_{\varepsilon}^{f}$ is at most the number of subsets of $2^{N}$
of size $(1/2+\varepsilon)\cdot 2^{N}$, and the claim follows. ∎

Thus 4.1 shows that $\mathsf{List}_{\varepsilon}^{f}$ is finite, although the
upper bound on $L(\varepsilon)$ is doubly-exponential in $n$. In Theorem 1.2,
we will prove that $L(\varepsilon)$ is independent of $n$, and is a polynomial
of $1/\varepsilon$.
Next, we show that

##### The underlying group is finite

We will simplify our situation by showing that we can assume without loss of
generality that $G$ is a finite Abelian group. This will allow us to decompose
$G$ as a finite product of cyclic groups of prime order and argue about
combinatorial bound by considering the projection on each of these groups.

######  Claim 4.2.

Let $f:\\{0,1\\}^{N}\to G$ be a function which is $(1/2-\varepsilon)$-close to
$\mathcal{P}_{1}$, for $\varepsilon>0$. Then there exists a finite group
$G^{\prime}$ and a function $f^{\prime}:\\{0,1\\}^{N}\to G^{\prime}$ such that
$|\mathsf{List}^{f}_{\varepsilon}|\leq|\mathsf{List}^{f^{\prime}}_{\varepsilon}|$.

The idea of the proof is as follows. We use 4.1 to first argue that there
exists a finitely generated subgroup of $G$ such that all the coefficients of
the polynomials in $\textsf{List}^{f}_{\varepsilon}$ are in this subgroup.
Then to go from a finitely generated subgroup to a finite group, we simply
“truncate” the group elements by going modulo a large enough number.

###### Proof.

We will first prove the above claim for a finitely generated subgroup
$G^{\prime\prime}\subseteq G$ and then describe how to find a finite group
$G^{\prime}$ (not necessarily a subgroup) that still meets the above
conditions. We define $G^{\prime\prime}$ as the subgroup generated by the
evaluations of polynomials in $\mathsf{List}_{\varepsilon}^{f}$ and $f$, i.e.,

$G^{\prime\prime}:=\langle\\{P(\mathbf{x}):\mathbf{x}\in\\{0,1\\}^{N}\text{
and
}P\in\mathsf{List}^{f}_{\varepsilon}\\}\cup\\{f(\mathbf{x}):\mathbf{x}\in\\{0,1\\}^{N}\\}\rangle,$

where $\langle S\rangle$ denotes the subgroup generated by the elements of a
subset $S\subseteq G$. We define $f^{\prime\prime}:\\{0,1\\}^{N}\to
G^{\prime\prime}$ as $f^{\prime\prime}(\mathbf{x})=f(\mathbf{x})$.
Let $\mathsf{List}^{f}_{\varepsilon}=\\{P_{1},\dots,P_{t}\\}$ for some integer
$t$; here we are using 4.1 which says that the list is of finite size (even
for infinite groups). We define $P^{\prime\prime}_{i}:\\{0,1\\}^{N}\to
G^{\prime\prime}$ as $P^{\prime\prime}_{i}(\mathbf{x})=L_{i}(\mathbf{x})$ for
each $P_{i}\in\mathsf{List}^{f}_{\varepsilon}$. Since $P_{i}(\mathbf{x})\in
G^{\prime\prime}$ for all $\mathbf{x}\in\\{0,1\\}^{N}$, we observe that all
the coefficients of $P_{i}$ are in $G^{\prime\prime}$. Hence,
$P^{\prime\prime}_{i}$ is a linear polynomial in $G^{\prime\prime}$, whose
distance from $f^{\prime\prime}$ is $(1/2-\varepsilon)$, i.e.,
$P^{\prime\prime}_{i}\in\mathsf{List}^{f^{\prime\prime}}_{\varepsilon}$.
Moreover, $P^{\prime\prime}_{i}$ for $i\in[t]$ are all distinct functions.
Hence,
$|\mathsf{List}^{f}_{\varepsilon}|\leq|\mathsf{List}^{f^{\prime\prime}}_{\varepsilon}|$.

Now by the classification of finitely generated Abelian groups,
$G^{\prime\prime}=\mathbb{Z}^{r}\times\mathbb{Z}_{r_{1}}\times\mathbb{Z}_{r_{2}}\times\dots\times\mathbb{Z}_{r_{k}}$
for some integers $r,k\geq 0$ and $r_{1},\dots,r_{k}\geq 2$. If $r=0$, we can
take $G^{\prime}=G^{\prime\prime}$ and that finishes the proof. Otherwise, we
let

$M:=2\cdot\max\\{\\{|P^{\prime\prime}_{i}(\mathbf{x})_{j}|:i\in[t],j\in[r],\mathbf{x}\in\\{0,1\\}^{N}\\}\cup\\{|f^{\prime\prime}(\mathbf{x})_{j}|:j\in[r],\mathbf{x}\in\\{0,1\\}^{N}\\}\\}+1$

where $a_{j}\in\mathbb{Z}$ denotes the $j$-th coordinate of $a$, for $a\in
G^{\prime\prime}$ and $j\in[r]$. This choice of $M$ is to ensure that no two
distinct elements among the evaluations of $P^{\prime\prime}_{i}$’s and
$f^{\prime\prime}$ are equal modulo $M$. We take
$G^{\prime}=\mathbb{Z}_{M}^{r}\times\mathbb{Z}_{r_{1}}\times\mathbb{Z}_{r_{2}}\times\dots\times\mathbb{Z}_{r_{k}}$
and define a homomorphism $\phi:G^{\prime\prime}\to G^{\prime}$ by applying
the map $x\mapsto x\mod M$ to the first $r$ coordinates of the input and the
identity map on the remaining coordinates. Let $f^{\prime}:\\{0,1\\}^{N}\to
G^{\prime}$ be defined as
$f^{\prime}(\mathbf{x})=\phi(f^{\prime\prime}(\mathbf{x}))$. For $i\in[t]$, if
$P^{\prime\prime}_{i}(\mathbf{x})=a^{(i)}_{0}+a^{(i)}_{1}x_{1}+\ldots+a^{(i)}_{N}x_{N}$
we define $P_{i}^{\prime}:\\{0,1\\}^{N}\to G^{\prime}$ as
$P_{i}^{\prime}(\mathbf{x})=\phi(a_{0}^{(i)})+\phi(a_{1}^{(1)})x_{1}+\phi(a_{2}^{(i)})x_{2}+\dots+\phi(a_{N}^{(i)})x_{N}$.
As for $\mathbf{x}\in\\{0,1\\}^{N}$,
$f^{\prime\prime}(\mathbf{x})=P^{\prime\prime}_{i}(\mathbf{x})$ implies that
$f^{\prime}(\mathbf{x})=P_{i}^{\prime}(\mathbf{x})$ and since $P^{\prime}_{i}$
is a linear polynomials over $G^{\prime}$, we have that
$P_{i}^{\prime}\in\mathsf{List}^{f^{\prime}}_{\varepsilon}$. Further, since
all the initial $r$ coordinates of the coefficients of $P^{\prime\prime}_{i}$
are at most $M$ in absolute value to begin with, we get that
$P_{i}^{\prime}\neq P_{j}^{\prime}$ for $i\neq j$. That is,
$|\mathsf{List}^{f^{\prime}}_{\varepsilon}|\geq
t=|\mathsf{List}^{f}_{\varepsilon}|$.

∎

Hence to obtain an upper bound on $|{\mathsf{List}^{f}_{\varepsilon}}|$, it
suffices to upper bound $|{\mathsf{List}^{f^{\prime}}_{\varepsilon}}|$.
Therefore, without loss of generality, for the rest of the proof we will
assume that $G$ is a finite Abelian group.
Now we describe the third step towards proving Theorem 1.2. Using the
structure theorem for finite Abelian groups, we know that $G$ can be written
as a product of finitely many cyclic $p$-groups111111For a prime $p$, a
$p$-group is a group in which every element has order a power of $p$. For a
cyclic group, this is just $\mathbb{Z}_{p^{k}}$ for some non-negative integer
$k$.. We decompose $G$ as follows:

$\displaystyle G=G_{1}\times G_{2}\times G_{3},$

where $G_{1}$ is product of $2$-groups, $G_{2}$ is a product of $3$-groups and
$G_{3}$ is a product of $p$-groups for $p\geq 5$. Let $f:\\{0,1\\}^{n}\to G$
be a polynomial, then $f=(f_{1},f_{2},f_{3})$, where $f_{i}:\\{0,1\\}^{n}\to
G_{i}$. We will prove a combinatorial list decoding bound for each $f_{i}$,
and then the product of these bounds will be an upper bound on
$|\mathsf{List}_{\varepsilon}^{f}|$. We have two cases - in the first case, we
provide an upper bound for $G_{1}$ and $G_{2}$, and in the second case, we
provide an upper bound for $G_{3}$. We state the upper bounds formally below.

######  Theorem 4.3 (Combinatorial bound for product of $2$ and $3$-groups).

Let $G$ be a product of finitely many $q$-groups, where
$q\in\left\\{2,3\right\\}$ and let $f:\\{0,1\\}^{n}\to G$ be any function.
Then, $|\mathsf{List}_{\varepsilon}^{f}|\leq\mathrm{poly}(1/\varepsilon)$.

######  Theorem 4.4 (Combinatorial Bound for Product of $p$-groups ($p\geq
5$)).

Let $G$ be a product of finitely many $p$-groups, where $p\geq 5$ and let
$f:\\{0,1\\}^{n}\to G$ be any function. Then,
$|\mathsf{List}_{\varepsilon}^{f}|\leq\mathrm{poly}(1/\varepsilon)$.

Assuming Theorem 4.3 and Theorem 4.4, we immediately get Theorem 1.2 because
if $P=(P_{1},P_{2},P_{3})\in\mathsf{List_{\varepsilon}^{f}}$, then for each
$i\in[3]$, $P_{i}$ must be in $\mathsf{List}_{\varepsilon}^{f_{i}}$. In the
next subsection, we prove Theorem 4.4 and in the subsection after that, we
prove Theorem 4.3.

###  4.1 Combinatorial Bound for Product of $p$-groups ($p\geq 5$)

In this subsection, we prove a particular case for the third step towards
proving Theorem 1.2. We will prove Theorem 4.4. We start by proving a result
on the sparsity of a polynomial, using an anti-concentration lemma (see Lemma
4.7).

####  4.1.1 Sparsity and Anti-concentration

Recall that a character of a finite Abelian group $G$ is a homomorphism from
$G$ to $\mathbb{C^{*}}$. For a subgroup $H$ of $G$, the characters of $H$ can
be extended to obtain characters of $G$ (we refer to [Con] for details). The
following theorem is a well-known fact about the extensions of characters of a
subgroup to characters of the group (see [Con, Theorem 3.4]).

######  Theorem 4.5.

Let $G$ be a finite Abelian group and $H$ be a subgroup of $G$. Then each
character of $H$ can be extended to a character of $G$ in $|G|/|H|$ ways.

An immediate corollary of the above theorem is the following.

######  Corollary 4.6.

Let $G$ be a finite Abelian group and $a\in G$ such that
$\text{order}(a)=r\geq 1$. Let $\chi$ be a randomly chosen character of $G$,
we have

$\displaystyle\Pr_{\chi}[\chi(a)=e^{\frac{2\pi ki}{r}}]=\frac{1}{r}$

for all $k\in\\{0,\dots,(r-1)\\}$.

###### Proof.

Let $H=\langle a\rangle$, be the cyclic group generated by $a$. The characters
of $H$ are $e^{\frac{2\pi ki}{r}}$ for $k\in\\{0,\dots,(r-1)\\}$. By Theorem
4.5, each of these characters has exactly $|G|/r$ many extensions to
characters of $G$. The corollary follows since $G$ has $|G|$ many characters.
∎

Next, we prove an important result regarding linear polynomials over groups
that are a product of $p$-groups for $p\geq 5$. This lemma, which reflects
certain anti-concentration properties of linear polynomials over such groups,
is the only part of the proof of Theorem 4.4 that uses something about the
structure of the group. The following lemma says that if two distinct linear
polynomials agree on a large fraction of points, then their respective
coefficient vector must be quite similar.

Given a polynomial $P\in\mathcal{P}_{1},$ we use $\mathrm{vars}(P)$ to denote
the set of variables with non-zero coefficient in $P.$

######  Lemma 4.7 (Anti-concentration lemma).

Let $G$ be a product of finitely many $p$-groups where $p\geq 5$ and let
$P_{i},P_{j}:\\{0,1\\}^{n}\to G$ be two distinct linear polynomials. If
$P_{i}$ and $P_{j}$ agree on at least $(1/4-0.001)$-fraction of
$\\{0,1\\}^{n}$, then $|\mathrm{vars}(P_{i}-P_{j})|\leq C_{0}$, where
$C_{0}\geq 4500$ is a constant.

###### Proof.

Let $\tilde{P}(\mathbf{x})=P_{i}(\mathbf{x})-P_{j}(\mathbf{x})$ for all
$\mathbf{x}\in\\{0,1\\}^{n}$. Thus
$\Pr_{\mathbf{x}\in\\{0,1\\}^{n}}[\tilde{P}(x)=0]=1-\delta(P_{i},P_{j})\geq
1/4-0.001$. Let $\tilde{P}(\mathbf{x})=\sum_{i=1}^{k}a_{i}x_{j_{i}}+a_{0}$
where, for all $i\in\\{0,\ldots,k\\}$, $a_{i}\in G$ are non-zero elements and
$j_{i}\in[n]$. Our goal is to upper bound $k$ using the hypothesis of the
lemma.

Let $\widehat{G}$ be the group of characters of $G$. Recall [Con, Theorem 4.1]
that $\tilde{P}(\mathbf{x})=0$ then

$\mathbb{E}_{\chi\in\widehat{G}}[\chi(\tilde{P}(x))]=\left\\{\begin{array}[]{cc}1&\text{if
$\tilde{P}(\mathbf{x})=0$,}\\\ 0&\text{otherwise.}\end{array}\right.$

Using this, we have

$\displaystyle\frac{1}{4}-0.001$
$\displaystyle\leq\Pr_{\mathbf{x}\in\\{0,1\\}^{n}}[\tilde{P}(\mathbf{x})=0]$
$\displaystyle=\left|\mathbb{E}_{\chi\in\widehat{G}}\mathbb{E}_{\mathbf{x}\in\\{0,1\\}^{n}}\chi(\tilde{P}(x))\right|$
$\displaystyle\leq\mathbb{E}_{\chi\in\widehat{G}}\left|\mathbb{E}_{\mathbf{x}\in\\{0,1\\}^{n}}\chi(\tilde{P}(x))\right|$
(by triangle inequality)
$\displaystyle=\mathbb{E}_{\chi\in\widehat{G}}\left|\mathbb{E}_{\mathbf{x}\in\\{0,1\\}^{n}}\prod_{i=1}^{k}\chi(a_{i}x_{j_{i}})\right|$
(using multiplicativity of $\chi$ and $|\chi(a_{0})|=1$)
$\displaystyle=\mathbb{E}_{\chi\in\widehat{G}}\left|\prod_{i=1}^{k}\left(\frac{1+\chi(a_{i})}{2}\right)\right|$
$\displaystyle=\mathbb{E}_{\chi\in\widehat{G}}\left[\prod_{i=1}^{k}\left|\frac{1+\chi(a_{i})}{2}\right|\right].$
(11)

The argument of a complex number $z\in\mathbb{C}$ of absolute value $|z|=1$,
denoted by $\text{arg}(z)$, is the unique real number $\alpha\in(-\pi,\pi]$
such that $z=e^{i\alpha}$.

We say that $a$ is “bad” for $\chi$ if $|\text{arg}(\chi(a))|<(2\pi)/20$.
Thus, if $\text{order}(a)=r\geq 5$, then from Corollary 4.6 the probability
that a random $\chi$ is bad for $a$ is at most $1/5$. Since
$\tilde{P}(\mathbf{x})=\sum_{i=1}^{k}a_{i}x_{j_{i}}+a_{0}$ where each
$a_{i}\in G$ ($i\in[k]$) has order at least $5$, the expected number of
$a_{i}$’s that are bad for a randomly chosen $\chi$ is at most $k/5$.

Let $E$ be the event that there are at least $(\beta k)$ $a_{i}$’s that are
not bad for a randomly chosen $\chi$, where $\beta$ is a suitable constant to
be fixed later. By Markov’s inequality, $\Pr[\overline{E}]\leq
1/(5(1-\beta))$. We have

$\displaystyle\mathbb{E}_{\chi\in\widehat{G}}\left[\prod_{i=1}^{k}\left|\frac{1+\chi(a_{i})}{2}\right|\right]$
$\displaystyle=\mathbb{E}\left[\left(\prod_{i=1}^{k}\left|\frac{1+\chi(a_{i})}{2}\right|\right)\mid
E\right]\Pr[E]+\mathbb{E}\left[\left(\prod_{i=1}^{k}\left|\frac{1+\chi(a_{i})}{2}\right|\right)\mid\overline{E}\right]\Pr[\overline{E}]$
$\displaystyle\leq\mathbb{E}\left[\left(\prod_{i=1}^{k}\left|\frac{1+\chi(a_{i})}{2}\right|\right)\mid
E\right]\Pr[E]+\Pr[\overline{E}]$
$\displaystyle\leq\mathbb{E}\left[\left(\prod_{i=1}^{k}\left|\frac{1+\chi(a_{i})}{2}\right|\right)\mid
E\right]+\frac{1}{5(1-\beta)},$

where the first inequality uses the fact that $|(1+\chi(a)/2|\leq 1$ for all
$\chi\in\widehat{G}$ and $a\in G$. Conditioned on $E$, at least $(\beta k)$
many $a_{i}$’s satisfy $|\text{arg}(\chi(a_{i}))|\geq(2\pi)/20$. For any such
$a_{i}$,

$\displaystyle\left|\frac{1+\chi(a_{i})}{2}\right|=1/2\cdot\sqrt{\left(1+\cos(\text{arg}(a_{i}))\right)^{2}+\sin(\text{arg}(a_{i}))^{2}}=|\cos(\text{arg}(a_{i})/2)|\leq\cos(\pi/20).$

Combining with Equation 11 we have

$\displaystyle\frac{1}{4}-0.001\leq\mathbb{E}_{\chi\in\widehat{G}}\left[\prod_{i=1}^{k}\left|\frac{1+\chi(a_{i})}{2}\right|\right]\leq\cos(\pi/20)^{\beta
k}+\frac{1}{5(1-\beta)}.$

Choosing $\beta$ to be $1/9$, we have a contradiction if $k$ is larger than
$C_{0}$. ∎

In Lemma 4.7, we proved that if two distinct linear polynomials agree on
nearly $1/4$-fraction of the Boolean cube, then their difference is a sparse
polynomial. Intuitively, two linear polynomials in
$\mathsf{List}_{\varepsilon}^{f}$ also agree on a large fraction because both
of them agree with $f$ on nearly $1/2$-fraction of the Boolean cube. We will
use this observation along with Lemma 4.7 to reduce to sparse polynomials.

##### Many of the polynomials are sparse

We will now reduce our problem of proving an upper bound on
$|\mathsf{List}_{\varepsilon}^{f}|$ to the setting of proving a combinatorial
bound when it is also known that the polynomials in the list are ‘sparse’, in
the sense that they only have a few non-zero coefficients.

Suppose $\mathsf{List}_{\varepsilon}^{f}=\left\\{P_{1},\ldots,P_{t}\right\\}$.
We define a graph $\mathcal{G}=(V,E)$ with $|V|=t$. The vertices in $V$
represents the codewords in $\mathsf{List}_{\varepsilon}^{f}$ – in particular
$i^{th}$ vertex corresponds to $P_{i}$. Edge $(i,j)$ exists if and only if
$|\mathrm{vars}(P_{i}-P_{j})|\leq C_{0}$, where $C_{0}$ is the absolute
constant from Lemma 4.7.

In other words, two linear polynomials $P_{i}$ and $P_{j}$ are related via an
edge if $P_{i}-P_{j}$ is supported on at a most constant, $C_{0}$, many
variables.

We will show that $\mathcal{G}$ has a vertex of large degree (in terms of the
number of vertices $t$ of $\mathcal{G}$) and then instead of upper bounding
$t=|\mathsf{List}_{\varepsilon}^{f}|$, we will upper bound the largest degree
of $\mathcal{G}$. To be a bit more precise, in Lemma 4.10, we will show that
$\mathcal{G}$ has a vertex of degree $\Omega(t)$. It will then suffice to show
that the number of polynomials neighbouring any vertex in $\mathcal{G}$ is at
most $\mathrm{poly}(1/\varepsilon)$.

To prove Lemma 4.10, we will use the following lemma which can be proved by
forming the independent set greedily.

######  Lemma 4.8.

Any undirected graph on $t$ vertices contains either an independent set of
size $t/(\Delta+1)$ if all the vertices are of degree at most $\Delta$.

We also need the following lemma, a proof of which can found in [Juk11, Lemma
2.1].

######  Lemma 4.9.

Let $A_{1},\dots,A_{k}$ be sets of cardinality $r$ and let
$X=\cup_{i=1}^{k}A_{i}$. If $|A_{i}\cap A_{j}|\leq t$ for all $i\neq j\in[k]$,
then $|X|\geq(r^{2}k)/(r+(k-1)t)$.

Now we will prove that the graph $\mathcal{G}$ as defined above, has a vertex
of degree at least $\Omega(t)$.

######  Lemma 4.10 ($\mathcal{G}$ has a vertex of large degree).

Let $\mathcal{G}=(V,E)$ be the graph as defined above on $t$ vertices. Then
there exists a vertex $v\in V$ of degree $\Omega(t)$.

###### Proof.

We will show that there does not exist an independent set of size $k$ in
$\mathcal{G}$, where $k$ is a large enough constant. Then applying Lemma 4.8,
we get that there is a vertex of degree at least $(t/k)-1\geq\Omega(t)$.
Let $v_{1},\dots,v_{k}\in V$ be any $k$ distinct vertices. We will show that
$\left\\{v_{1},\dots,v_{k}\right\\}$ do not form an independent set for a
large enough constant $k$. Recall that the vertex $v_{i}$ corresponds to some
linear function $P_{j_{i}}\in\mathsf{List}_{\varepsilon}^{f}$. Let
$A^{\prime}_{i}=\\{x:f(\mathbf{x})=P_{j_{i}}(\mathbf{x})\\}$ and thus
$|A^{\prime}_{i}|\geq(1/2\cdot 2^{n})$. Also, let $A_{i}\subset
A^{\prime}_{i}$ such that $|A_{i}|=(1/2\cdot 2^{n})$. Now we use Lemma 4.9 to
upper bound $k$ assuming for all $i_{1},i_{2}\in[k]$, $|A_{i_{1}}\cap
A_{i_{2}}|\leq((1/4-0.001)\cdot 2^{n})$. Since $|\cup_{i=1}^{k}A_{i}|\leq
2^{n}$, we have

$\displaystyle 2^{n}\geq\frac{(1/2\cdot 2^{n})^{2}\cdot k}{(1/2\cdot
2^{n})+(k-1)\cdot((1/4-0.001)\cdot 2^{n})}$

which implies that

$\displaystyle 1/4+0.001\geq k\cdot 0.001.$

Thus choosing $k$ to be constant greater than $4002$ implies that there exists
$i_{1},i_{2}\in[k]$ such that $|A_{i_{1}}\cap A_{i_{2}}|>(1/4-0.001)\cdot
2^{n}$.

Since $\delta(P_{j_{i_{1}}},P_{j_{i_{2}}})\geq 1/2^{n}\cdot|A_{i_{1}}\cap
A_{i_{2}}|$ for all $i_{1},i_{2}\in[k]$, using Lemma 4.7 and the choice of
$C_{0}$ as discussed before, we get
$|\mathrm{vars}(P_{j_{i_{1}}}-P_{j_{i_{2}}})|\leq C_{0}$. In particular, the
corresponding vertices are adjacent in $\mathcal{G}$, contradicting the
assumption that $\\{v_{1},\ldots,v_{k}\\}$ is an independent set.

Thus we have shown no subset of $k$ vertices in $\mathcal{G}$ forms an
independent set and this concludes the proof. ∎

Let $v\in V$ be the vertex $\mathcal{G}$ given by Lemma 4.10 with degree
$m\geq\Omega(t)$. As discussed above, to prove a
$\mathrm{poly}(1/\varepsilon)$ upper bound on
$t=|\mathsf{List}_{\varepsilon}^{f}|$, it suffices to prove a
$\mathrm{poly}(1/\varepsilon)$ upper bound on $m$. Let $P_{0}$ be the linear
polynomial corresponding to the vertex $v$ and let $P_{1},P_{2},\dots,P_{m}$