be the linear polynomials in $\mathsf{List}_{\varepsilon}^{f}$ that are
adjacent to $P_{0}$ in $\mathcal{G}$. For every $i\in[m]$, we define a degree
$1$ polynomial $\tilde{P}_{i}:=P_{i}-P_{1}$, and we define
$\tilde{f}:=f-P_{0}$. Note that
$\delta(\tilde{P}_{i},\tilde{f})=\delta(P_{i},f)$, i.e.,
$\tilde{P}_{i}\in\mathsf{List}_{\varepsilon}^{\tilde{f}}$. Moreover, by the
definition of the graph $\mathcal{G}$, we have that
$|\mathrm{vars}(\tilde{P}_{i})|\leq C_{0}$ for all $i\in[m]$.

Let $\ell=|\bigcup_{i=1}^{m}\mathrm{vars}(\tilde{P}_{i})|$. We will say $\ell$
is small if $\ell\leq(1/\varepsilon)^{K}$, where $K=20$, and $\ell$ is large
otherwise. Depending on which case we are in, we use Lemma 4.11 or Lemma 4.13
below to show that $m\leq\mathop{\mathrm{poly}}(1/\varepsilon).$ This
completes the proof of Theorem 4.4 as we have already established that
$m\geq\Omega(t)$.

####  4.1.2 Union of Supports is Small

In this subsection, we prove that if the number of variables in the support of
polynomials in $\tilde{V}$ is small, then $m=|\tilde{V}|$ is small too. We
prove the following lemma.

######  Lemma 4.11 ($\ell$ is small).

Let $f:\\{0,1\\}^{n}\to G$ be a polynomial and let
$\mathcal{A}\subseteq\mathsf{List}_{\varepsilon}^{f}$ be a set of degree-$1$
polynomials satisfying the following property: There exists an absolute
constant $C$ such that for every $P\in\mathcal{A}$, $|\mathrm{vars}(P)|\leq
C$.
Let $\ell=|\bigcup_{P\in\mathcal{A}}\mathrm{vars}(P)|$. Then we have
$|\mathcal{A}|\leq O(\ell^{C}\cdot(1/\varepsilon))$.

###### Proof of Lemma 4.11.

Let $\mathcal{A}=\left\\{P_{1},\ldots,P_{m}\right\\}$. Choose any set
$T\subseteq\bigcup_{i=1}^{m}\mathrm{vars}(P_{i})$ of size $C$ and let
$\mathcal{A}_{T}\subseteq\mathcal{A}$ denote the subset of polynomials that
are supported only on (a subset of the) variables in $T$. We have,

$\displaystyle|\mathcal{A}|\leq\sum_{\begin{subarray}{c}T\subseteq\cup_{i=1}^{m}\mathrm{vars}(P_{i}):\\\
|T|=C\end{subarray}}|\mathcal{A}_{T}|.$ (12)

Let $M$ be an upper bound on all $|\mathcal{A}_{T}|$’s, thus

$\displaystyle|\mathcal{A}|\leq\binom{\ell}{C}M=O(\ell^{C}\cdot M).$ (13)

Fix an arbitrary $T\subseteq\bigcup_{i=1}^{m}\mathrm{vars}(P_{i})$ of size
$C$. Label the variables indexed by $T$ as
$\left\\{y_{1},\ldots,y_{|T|}\right\\}$ and the remaining variables as
$\left\\{z_{1},\ldots,z_{n-|T|}\right\\}$. 4.12 shows that there exists an
assignment $\mathbf{z}=\mathbf{b}$ such that $(\varepsilon/10)$-fraction of
$\mathcal{A}|_{\mathbf{z}=\mathbf{b}}$ are $\approx(1/2-\varepsilon)$-close to
$f|_{\mathbf{z}=\mathbf{b}}$, where $\mathcal{A}|_{\mathbf{z}}$ denotes that
every polynomial in $\mathcal{A}$ is restricted according to $\mathbf{z}$.

######  Claim 4.12.

There exists an assignment $\mathbf{b}\in\\{0,1\\}^{n-|T|}$ to the
$\mathbf{z}$ such that there is a subset $\mathcal{B}\subseteq\mathcal{A}_{T}$
satisfying the following properties:

  * •

For each $P\in\mathcal{B}$,
$\delta(P|_{\mathbf{z}=\mathbf{b}},f|_{\mathbf{z}=\mathbf{b}})\leq(1/2-\varepsilon/10)$,

  * •

$|\mathcal{B}|$ is at least $\varepsilon/10\cdot|\mathcal{A}_{T}|$.

Let us defer the proof of 4.12 for a while and see how to use 4.12 to finish
the proof of Lemma 4.11. Observe that for any polynomial in
$\tilde{P}\in\mathcal{B}$,
$\delta(\tilde{P},f|_{\mathbf{z}=\mathbf{b}})\leq(1/2-\varepsilon/10)$ and
$\tilde{P},f|_{\mathbf{z}=\mathbf{b}}$ depend only on $C$ variables. Thus by
applying 4.1 on $f|_{\mathbf{z}=\mathbf{b}}$, we get the following:

$\displaystyle(\varepsilon/10)\cdot|\mathcal{A}_{T}|\leq
2^{2^{C}}\;\Rightarrow\;M=\mathcal{O}(1/\varepsilon).$

Along with Equation 13, this completes the proof of Lemma 4.11. ∎

Now we give the proof of 4.12 and this will complete the proof of the case
when $\ell$ is small.

###### Proof of 4.12.

Fix any degree-$1$ polynomial $P\in\mathcal{A}_{T}$. Since
$\delta(P,f)\leq(1/2-\varepsilon)$, we have

$\displaystyle\Pr_{\mathbf{z}}\,\Pr_{\mathbf{y}}[f(\mathbf{y},\mathbf{z})\neq
P(\mathbf{y},\mathbf{z})]\leq\frac{1}{2}-\varepsilon,$

For an assignment $\mathbf{b}\in\\{0,1\\}^{n-|T|}$ of $\mathbf{z}$, let
$\rho_{\mathbf{b}}^{P}$ denote the distance between
$P|_{\mathbf{z}=\mathbf{b}}$ and $f|_{\mathbf{z}=\mathbf{b}}$, i.e.

$\displaystyle\rho_{\mathbf{b}}^{P}=\Pr_{\mathbf{y}}[\tilde{f}(\mathbf{y},\mathbf{b}),\neq
P(\mathbf{y},\mathbf{b})]$

So we get,

$\displaystyle\mathbb{E}_{\mathbf{b}}[\rho_{\mathbf{b}}^{P}]\leq\frac{1}{2}-\varepsilon$
$\displaystyle\Rightarrow\Pr_{\mathbf{b}}[\rho_{\mathbf{b}}^{P}>(1/2-\varepsilon/10)]\leq\frac{1/2-\varepsilon}{1/2-\varepsilon/10}$
(Markov’s Inequality)
$\displaystyle\Rightarrow\Pr_{\mathbf{b}}[\rho_{\mathbf{b}}^{P}\leq(1/2-\varepsilon/10)]\geq\varepsilon/10$

This implies that for $\mathbf{b}\sim U_{n-|T|}$, in expectation at least
$\varepsilon/10$ fraction of polynomials in $\mathcal{A}_{T}$ are
$(1/2-\varepsilon/10)$ close to $f|_{\mathbf{z}=\mathbf{b}}$. This implies the
existence of an assignment $\mathbf{b}\in\\{0,1\\}^{n-|T|}$ and a subset
$\mathcal{B}$ as claimed. ∎

####  4.1.3 Union of Supports is Large

In this subsection, we prove the complementary case to Lemma 4.11.

######  Lemma 4.13 ($\ell$ is large).

Let $f:\\{0,1\\}^{n}\to G$ be a polynomial and let
$\mathcal{A}\subseteq\mathsf{List}_{\varepsilon}^{f}$ be a set of degree $1$
polynomials such that $\ell=|\bigcup_{P\in\mathcal{A}}\mathrm{vars}(P)|$. If
$|\mathrm{vars}(P)|\leq C_{0}$ for all $P\in\mathcal{A}$ and
$\ell\geq(1/\varepsilon)^{20}$ (i.e. $\ell$ is large), then
$|\mathcal{A}|=O((1/\varepsilon)^{20C_{0}})$.

###### Proof.

Let $\mathcal{A}=\left\\{P_{1},\ldots,P_{m}\right\\}$ where for contradiction
we assume that $m\geq(C_{0}/\varepsilon)^{20C_{0}}$. Let $B$ denote the
following subset of variables:

$\displaystyle
B:=\left\\{i\in\bigcup_{j=1}^{m}\mathrm{vars}(P_{j})\;\;\middle|\;\;\\#j\,\text{
such that }\,\mathrm{vars}(P_{j})\ni i\text{~{}is at
least~{}}\varepsilon^{10}\cdot m\right\\}.$

Since $|\mathrm{vars}(P_{j})|\leq C_{0}$ for all $j\in[m]$, $|B|$ has at most
$C_{0}/\varepsilon^{10}$ variables. We call a polynomial $P_{j}$ an _ignore
polynomial_ if $\mathrm{vars}(P_{j})\subset B$. The number of ignore
polynomials is at most
$O((C_{0}/\varepsilon^{10})^{C_{0}}\cdot(1/\varepsilon))$ using Lemma 4.11.
Let $\mathcal{A}_{0}$ denote the set $\mathcal{A}$ obtained after removing the
ignore polynomials, and we have $|\mathcal{A}_{0}|\geq m/2$.

To prove the claim, we construct a set
$\mathcal{A}^{\prime}\subseteq\mathcal{A}_{0}$ satisfying the following
properties:

  * •

Each polynomial in $\mathcal{A}^{\prime}$ depends on a variable outside $B$,
i.e. for any $Q\in\mathcal{A}^{\prime}$, $\mathrm{vars}(Q)$ is not a proper
subset of $B$.

  * •

For any two distinct polynomials in $\mathcal{A}^{\prime}$, their pairwise
intersection lies inside $B$, i.e. if $Q_{i},Q_{j}\in\mathcal{A}^{\prime}$ are
two distinct polynomials, then,

$\displaystyle(\mathrm{vars}(Q_{i})\setminus
B)\cap(\mathrm{vars}(Q_{j})\setminus B)=\emptyset.$ (14)

In other words, if the variables in $B$ are fixed to an assignment, then the
resulting polynomials in $\mathcal{A}^{\prime}$ are supported on pairwise
disjoint sets of variables.

  * •

$|\mathcal{A}^{\prime}|=\Omega(1/\varepsilon^{10})$.

We will construct $\mathcal{A}^{\prime}$ iteratively, initially
$\mathcal{A}^{\prime}=\emptyset$. Consider any polynomial
$Q_{1}\in\mathcal{A}_{0}$ and let $B_{1}$ denote the set
$\mathrm{vars}(Q_{1})\setminus B$. By definition of $B$, each variable in
$B_{1}$ occurs in variable sets of at most $\varepsilon^{10}\cdot m$
polynomials and $|B_{1}|\leq C_{0}$. Thus there are at most
$(\varepsilon^{10}\cdot m)\cdot C_{0}$ many polynomials in $\mathcal{A}_{0}$
containing a variable in $B_{1}$; remove the polynomials from
$\mathcal{A}_{0}$ and also update
$\mathcal{A}^{\prime}=\mathcal{A}^{\prime}\cup\\{Q_{1}\\}$. Observe that the
size of the resulting $\mathcal{A}_{0}$ is at least
$m/2-(C_{0}\cdot\varepsilon^{10}\cdot m)$. Thus, in a similar manner and using
the assumption that $m\geq\mathop{\mathrm{poly}}(1/\varepsilon)$ for suitably
large polynomial of $(1/\varepsilon)$, we can choose $Q_{2}$ from
$\mathcal{A}_{0}$ in the next iteration, and so on to obtain
$\mathcal{A}^{\prime}=\\{Q_{1},Q_{2},\dots,Q_{r}\\}$ where
$r=\Omega(1/\varepsilon^{10})$.

Now choose $\mathbf{x}\in\\{0,1\\}^{n}$ uniformly at random and consider

$\displaystyle\Pr_{\mathbf{x}}\left[\exists i^{\star}\in[r]:\frac{\sum_{i\neq
i^{\star},i=1}^{r}1[Q_{i^{\star}}(\mathbf{x})=Q_{i}(\mathbf{x})]}{r}\geq(1/2+\varepsilon/10-1/r)\right].$
(15)

The above equation denotes the probability that at a random $\mathbf{x}$, some
$Q_{i^{\star}}$ agrees with a large fraction of other $Q(i)$’s. Going forward,
the proof strategy is to upper bound and lower bound the above probability to
get a contradiction.

First for the upper bound, observe that for a random
$\mathbf{x}\in\\{0,1\\}^{n}$ conditioned on
$\mathbf{x}|_{B}=\mathbf{a}\in\\{0,1\\}^{|B|}$, by Equation 14,
$Q_{i}(\mathbf{x})$’s are independent random variables as they depend on
disjoint set of variables. In particular, for a fixed $j\in[r]$ and $i\neq
j\in[r]$,
$\Pr_{\mathbf{x}}[Q_{i}(\mathbf{x})=Q_{j}(\mathbf{x})\mid\mathbf{x}|_{B=a}]\leq
1/2$ (by the Schwartz-Zippel Lemma) for all $a\in\\{0,1\\}^{|B|}$, and thus by
Chernoff bound,

$\displaystyle\Pr_{\mathbf{x}}\left[\frac{\sum_{i\neq
j,i=1}^{r}1[Q_{j}{(\mathbf{x})}=Q_{i}(\mathbf{x})]}{r}\geq(1/2+\varepsilon/10-1/r)\right]\leq\exp(-\varepsilon^{2}\cdot
r).$

Thus by union bound, the probability in Equation 15 is upper bounded by
$(r\cdot\exp(-\varepsilon^{2}\cdot r))=O(\exp(-(\varepsilon^{2}\cdot
r)/2))=O(\exp(-1/\varepsilon^{8}))$.

Next, we give a lower bound for the probability in Equation 15. Since each
$Q_{i}\in\mathcal{A}^{\prime}$, for $i\in[r]$, agrees with $f$ on at least
$(1/2+\varepsilon)$ fraction of $\\{0,1\\}^{n}$, we have

$\displaystyle\Pr_{i\in[r],\mathbf{x}\in\\{0,1\\}^{n}}[Q_{i}(\mathbf{x})\neq
f(\mathbf{x})]\leq(1/2-\varepsilon).$

From an argument similar to that of 4.12 we have that on at least
$(\varepsilon/10)$ fraction of $\mathbf{x}\in\\{0,1\\}^{n}$,
$\Pr_{i}[Q_{i}(\mathbf{x})\neq f(\mathbf{x})]\leq(1/2-\varepsilon/10)$. On
such an $\mathbf{x}$, there exists an $i^{\star}\in[r]$ such that
$Q_{i^{\star}}$ agrees with at least $(1/2+\varepsilon/10)r-1$ of
$Q_{1},\dots,Q_{r}$. In other words,

$\displaystyle\Pr_{\mathbf{x}}\left[\exists i^{\star}\in[r]:\frac{\sum_{i\neq
i^{\star},i=1}^{r}1[Q_{i^{\star}}(\mathbf{x})=Q_{i}(\mathbf{x})]}{r}\geq(1/2+\varepsilon/10-1/r)\right]\geq\varepsilon/10,$

which contradicts the upper bound. ∎

Summarizing the proof of Theorem 4.4 \- We reduced our problem to upper
bounding the list size of sparse polynomials (see Lemma 4.10). We then have
two cases, depending on the size of the union of variables in the support. In
the case where this is small (see Lemma 4.11), we upper bound the list size by
fixing some variables and using a union bound. For the second case (see Lemma
4.13), we show that we can treat the polynomials as independent random
variables and then use concentration inequalities.

###  4.2 Combinatorial Bound for $2$ and $3$-groups

In this subsection, we will prove a particular case for the third step towards
proving Theorem 1.2. We will prove Theorem 4.3. The proof uses similar
techniques as used in [DGKS08] to prove combinatorial bound for group
homomorphisms. We start by first recalling a definition from [DGKS08] of a set
system with some nice properties.

##### Special intersecting set systems.

The next definition is about special intersecting sets. Let
$S_{1},\ldots,S_{t}$ be subsets of universe $X$. For a set $S\subseteq X$, let
$\mu(S)$ denote the density of $S$, i.e. $\mu(S):=|S|/|X|$. For a subset of
indices $I\subseteq[t]$, let $S_{I}$ denote the common intersection of subsets
corresponding to indices in $I$, i.e. $S_{I}:=\bigcap_{i\in I}S_{i}$.

######  Definition 8 (Special intersecting sets [DGKS08]).

Let $\rho,\tau\in(0,1]$ be two numbers such that $\tau\leq\rho$ and $c$ is a
constant. Sets $S_{1},\ldots,S_{t}$ are said to be $(\rho,\tau,c)$-special
intersecting sets if they satisfy the following conditions:

  1. 1.

(Each subset is dense) For every subset $S_{i}$, $\mu(S_{i})$ is at least
$\rho$.

  2. 2.

(The pairwise intersection is small) For any two distinct subsets $S_{i}$ and
$S_{j}$, $\mu(S_{i}\cap S_{j})$ is at most $\rho$.

  3. 3.

Let $\mu(S_{i})=\rho+\alpha_{i}$. Then, $\sum_{i=1}^{t}\alpha_{i}^{c}\leq 1$.

  4. 4.

(Sunflower-structure) For subsets $I,J\in[t]$ where $J\subseteq I$ and
$|J|\geq 2$, if $\mu(S_{I})$ is strictly more than the threshold $\tau$, then
the common intersection $S_{I}$ is equal to $S_{J}$.

The following lemma is a crucial lemma in our technical results, which
essentially says that if we define a “potential” function on the density of
subsets and the subsets form certain special intersection sets, then we can
give an upper bound on the potential of the union of subsets. In particular,
if the density of each subset is “large”, then we can give an upper bound on
the number of subsets.

######  Lemma 4.14.

(Theorem 3.2 of [DGKS08]). Fix any constant $C$. Then there exists a constant
$D$ (depending on $C$) satisfying the following: Suppose $S_{1},\ldots,S_{t}$
are $(\rho,\rho^{2},C)$-special intersection sets for $\rho>0$ and
$\mu(S_{i})=\rho+\alpha_{i}$. Let
$\mu\left(\bigcup_{i}S_{i}\right)=\rho+\alpha$. Then,

$\displaystyle\sum_{i=1}^{t}\alpha_{i}^{D}\leq\alpha^{D}$

Recall that the Johnson bound (see e.g.[GRS23, Chapter 7]) allows us to bound
the list-decodability of codes based on their distance. In what follows, we
will need an analytic extension of this bound over $\mathbb{Z}_{2}$ and a
similar (but incomparable) statement over $\mathbb{Z}_{3}$.

######  Lemma 4.15 (Extended Johnson bound).

Let $q\in\left\\{2,3\right\\}$. There exists an absolute constant $C>0$ so
that the following holds. Let $f:\\{0,1\\}^{n}\rightarrow\mathbb{Z}_{q}$ be
any function and let $\Phi_{1},\ldots,\Phi_{t}:\\{0,1\\}^{n}\to\mathbb{Z}_{q}$
be distinct degree-$1$ polynomials such that for every $i\in[t]$, $f$ and
$\Phi_{i}$ agree on at least $1/2+\alpha_{i}$ fraction of $\\{0,1\\}^{n}$.
Then $\sum_{i=1}^{t}\alpha_{i}^{C}\leq 1$.

Note that the above statement immediately implies that the space
$\mathcal{P}_{1}$ is
$(\frac{1}{2}-\varepsilon,\mathop{\mathrm{poly}}(1/\varepsilon))$-list
decodable over $\mathbb{Z}_{2}$ and $\mathbb{Z}_{3}$ since the number of
indices $i$ for which $\alpha_{i}\geq\varepsilon$ can be at most
$(1/\varepsilon)^{C}$ as the sum $\sum_{i=1}^{t}\alpha_{i}^{C}$ has to be at
most 1. As we will see below, Lemma 4.15 is essentially equivalent to a
statement bounding the number of polynomials with agreement at least
$1/2+\varepsilon$. We will need the analytic formulation, however, to apply
the proof ideas of [DGKS08]. In the next subsection we will prove Lemma 4.15
and in the subsequent section, we will use Lemma 4.15 and special intersecting
set systems to prove Theorem 4.3.

####  4.2.1 Proof of Lemma 4.15 (Extended Johnson Bound)

Here we prove Lemma 4.15. When $q=2$, this follows immediately from the
standard “binary Johnson bound” (see, e.g. [DGKS08, Appendix A.1]). In order
to prove it for $q=3$, we will first prove a combinatorial bound in the
special case that the underlying group is $\mathbb{Z}_{3}$ and then Lemma 4.15
will follow from it.
We first show that for any $\varepsilon>0$, the number of $\Phi_{i}$’s for
which $\alpha_{i}\geq\varepsilon$ is bounded by
$\mathop{\mathrm{poly}}(1/\varepsilon)$.

######  Claim 4.16 (Combinatorial bound for $\mathbb{Z}_{3}$).

Let $\varepsilon>0$ and $f:\\{0,1\\}^{n}\to\mathbb{Z}_{3}$ be any function.
Then, $|\mathsf{List}_{\varepsilon}^{f}|\leq\mathrm{poly}(1/\varepsilon)$.

Before proving 4.16, let’s see how 4.16 implies Lemma 4.15.

###### Proof of Lemma 4.15.

For any $j\in\mathbb{N}$, let $B_{j}$ represent the following subset of
$\mathsf{List}_{\varepsilon}^{f}$:

$\displaystyle
B_{j}=\left\\{i\in[t]\;\middle|\;\frac{1}{2^{j+1}}<\alpha_{i}\leq\frac{1}{2^{j}}\right\\},$

i.e. we partition $\mathsf{List}_{\varepsilon}^{f}$ depending on how high the
agreement is with $f$. Let $c\in\mathbb{N}$ be a constant such that
$t\leq\left(1/\varepsilon\right)^{c}$ in the conclusion of 4.16. Then taking
$\varepsilon=1/2^{j+1}$ and applying 4.16, we get that the size of $B_{j}$ is
at most $\left(2^{j+1}\right)^{c}$ for all $j\in\mathbb{N}$. Therefore,

$\displaystyle\sum_{i=1}^{t}\alpha_{i}^{3c}=\sum_{j\geq 1}\sum_{i\in
B_{j}}\alpha_{i}^{3c}\leq\sum_{j\geq 1}\left\lvert
B_{j}\right\rvert\cdot\left(\frac{1}{2^{j}}\right)^{3c}\leq\sum_{j\geq
1}\left(\dfrac{1}{2^{j}}\right)^{c}\leq 1.$

Setting $C=3c$, we get that $\sum_{i=1}^{t}\alpha_{i}^{C}\leq 1$, and this
completes the proof of Lemma 4.15 (assuming 4.16). ∎

#####

In the rest of the section, we will prove 4.16. We will first prove the
following lemma, which is based on the proof of the binary Johnson bound
mentioned above, but also uses some anti-concentration properties over
$\mathbb{Z}_{3}.$

######  Lemma 4.17.

Let $f:\\{0,1\\}^{n}\to\mathbb{Z}_{3}$ be an arbitrary function and
$\Phi_{1},\Phi_{2},\dots,\Phi_{t}:\\{0,1\\}^{n}\to\mathbb{Z}_{3}$ be distinct
linear polynomials satisfying the following properties:

  1. 1.

For all $i\in[t]$, $\delta(f,\Phi_{i})\leq 1/2$.

  2. 2.

For all $i\neq j\in[t]$, $|\mathrm{vars}(\Phi_{i}-\Phi_{j})|\geq 6$.

Then $t\leq 31$ i.e., a constant.

###### Proof.

Let $\omega\in\mathbb{C}$ be a primitive cube root of unity. Let
$\mathbf{u}\in\mathbb{C}^{2^{n}}$ be defined as
$u_{\mathbf{x}}=\omega^{f(\mathbf{x})}$ and for $i\in[t]$, define
$\mathbf{v}^{(i)}\in\mathbb{C}^{2^{n}}$ as
$v^{(i)}_{\mathbf{x}}=\omega^{\Phi_{i}(\mathbf{x})}$. As $f$ and $\Phi_{i}$
agree on at least $1/2$ fraction of points, we have

$\displaystyle\textnormal{Re}\left(\left\langle\mathbf{u},\mathbf{v}^{(i)}\right\rangle\right)$
$\displaystyle=\sum_{\mathbf{x}}\textnormal{Re}\left(\omega^{f(\mathbf{x})-\Phi_{i}(\mathbf{x})}\right)$
$\displaystyle\geq 2^{n-1}\cdot{\left(1-1/2\right)}=2^{n-2},$

where the last inequality uses the fact that
$f(\mathbf{x})-\Phi_{i}(\mathbf{x})=0$ for at least $2^{n-1}$ choices of
$\mathbf{x}$. For arbitrary $i\neq j\in[t]$, let
$\Psi(\mathbf{x}):=\Phi_{i}(\mathbf{x})-\Phi_{j}(\mathbf{x})$ be equal to
$a_{1}x_{1}+a_{2}x_{2}+\dots+a_{n}x_{n}+a_{0}$ where $a_{i}\in\mathbb{Z}_{3}$
for $i\in[n]$ and the number of indices $i$ with $a_{i}\neq 0$ is at least
$6$, by assumption. We now show that the vectors $\mathbf{v}^{(i)}$ and
$\mathbf{v}^{(j)}$ are “almost” orthogonal:

$\displaystyle\left\lvert\left\langle\mathbf{v}^{(i)},\mathbf{v}^{(j)}\right\rangle\right\rvert$
$\displaystyle=\left\lvert\sum_{\mathbf{x}}\omega^{\Phi_{i}(\mathbf{x})}\cdot{\omega^{-\Phi_{j}(\mathbf{x})}}\right\rvert$
$\displaystyle=2^{n}\cdot\left\lvert\operatorname*{\mathbb{E}}_{\mathbf{x}}[\omega^{a_{1}x_{1}+a_{2}x_{2}+\dots+a_{n}x_{n}+a_{0}}]\right\rvert$
$\displaystyle=2^{n}\cdot\prod_{i\in[n]}\left\lvert\operatorname*{\mathbb{E}}_{x_{i}}[\omega^{a_{i}x_{i}}]\right\rvert$
$\displaystyle=2^{n}\cdot\prod_{i\in[n]}\left\lvert\frac{1+\omega^{a_{i}}}{2}\right\rvert$
$\displaystyle=2^{n}\cdot\left(\frac{1}{2}\right)^{\left\lvert\\{i\in[n]:a_{i}\neq
0\\}\right\rvert}\leq 2^{n-5}.$

Combined with the fact that $\mathbf{u}$ has a “large” component along
$\mathbf{v}^{(i)}$ for every $i\in[t]$ i.e.,
$\textnormal{Re}\left(\left\langle\mathbf{u},\mathbf{v}^{(i)}\right\rangle\right)\geq
2^{n-2}$, this leads us to conclude that $t$ is a constant. To see this, let
$\mathbf{w}^{(i)}:=\frac{1}{\sqrt{2^{n}}}\left(\mathbf{v}^{(i)}-\mathbf{u}/4\right)$
for $i\in[t]$. Then we have

$\displaystyle\left\langle\mathbf{w}^{(i)},\mathbf{w}^{(i)}\right\rangle=\frac{1}{2^{n}}\left(2^{n}+2^{n}/16-\textnormal{Re}\left(\left\langle\mathbf{u},\mathbf{v}^{(i)}\right\rangle+\left\langle\mathbf{v}^{(i)},\mathbf{u}\right\rangle\right)/4\right)\leq
1+1/16-1/8=15/16,$

and

$\displaystyle\textnormal{Re}\left(\left\langle\mathbf{w}^{(i)},\mathbf{w}^{(j)}\right\rangle\right)$
$\displaystyle=\frac{1}{2^{n}}\left(\textnormal{Re}\left(\left\langle\mathbf{v}^{(i)},\mathbf{v}^{(j)}\right\rangle\right)+2^{n}/16-\textnormal{Re}\left(\left\langle\mathbf{u},\mathbf{v}^{(i)}\right\rangle+\left\langle\mathbf{v}^{(i)},\mathbf{u}\right\rangle\right)/4\right)$
$\displaystyle\leq 1/32+1/16-1/8=-1/32.$

Thus, we have

$0\leq\left\langle\sum_{i=1}^{t}\mathbf{w}^{(i)},\sum_{i=1}^{t}\mathbf{w}^{(i)}\right\rangle=\sum_{i=1}^{t}\left\langle\mathbf{w}^{(i)},\mathbf{w}^{(i)}\right\rangle+\sum_{i\neq
j}\textnormal{Re}\left(\left\langle\mathbf{w}^{(i)},\mathbf{w}^{(j)}\right\rangle\right)\leq
15t/16-(t^{2}-t)/32.$

Therefore $t\leq 31$.

∎

Now we finish the proof of 4.16 using Lemma 4.17.

###### Proof of 4.16.

The proof idea is to follow the same initial strategy as for groups with order
at least 5 from Section 4.1. To recall the setup, we have
$\mathsf{List}_{\varepsilon}^{f}=\left\\{L_{1},\ldots,L_{t}\right\\}$. We
construct an undirected graph $\mathcal{G}=(V,E)$ with $|V|=t$: the $i^{th}$
vertex in $V$ corresponds to the polynomial $L_{i}$. We add an edge $(i,j)$ in
$E$ iff $|\mathrm{vars}{(L_{i}-L_{j})}|\leq 5$.

Note that Lemma 4.17 implies that there is no independent set size greater
than $31$ in $\mathcal{G}$. Hence, by applying Lemma 4.8, we conclude that
there exists a vertex of degree at least $\Omega(t)$ in $\mathcal{G}$. Once we
have such a vertex, we proceed in the same manner as in the proof of Theorem
4.4 to finally get an upper bound of
$t\leq\mathop{\mathrm{poly}}(1/\varepsilon)$ on the number of linear
polynomials in $\mathsf{List}^{f}_{\varepsilon}$. ∎

####  4.2.2 Proof of Combinatorial Bound for a Product of $2$ and $3$-groups

In this subsection, we will prove Theorem 4.3. We will use $q$ for $2$ or $3$
in the rest of the subsection. To prove Theorem 4.3, we need the following
lemma, which is crucial to upper bound the list size using special-
intersecting sets.

######  Lemma 4.18.

The following holds true for any finite $q$-group $G.$ Let $f:\\{0,1\\}^{n}\to
G$ be any function. Let $\\{P_{1},\ldots,P_{t}\\}$ be the set of polynomials
in $\mathcal{P}_{1}(\\{0,1\\}^{n},G)$ that are $1/2$-close to $f.$ Then, if
$\delta(f,P_{i})=\frac{1}{2}-\alpha_{i}$ for each $i\in[t]$, we have

$\sum_{i=1}^{t}\alpha_{i}^{D}\leq 1$

for some absolute constant $D>0.$ In particular, the number of $i$ such that
$\delta(f,P_{i})\leq\frac{1}{2}-\varepsilon$ is at most $(1/\varepsilon)^{D}.$

Note that Theorem 4.3 follows immediately from Lemma 4.18 because a finite
product of $q$-groups is a $q$-group. In the remaining part of this
subsection, we are going to prove Lemma 4.18.

###### Proof of Lemma 4.18.

We will prove it via induction on the size of $G$. The constant $D$ is chosen
as follows. Let $C_{q}$ be the constant in the extended Johnson bound (Lemma
4.15), and let $D$ be the constant obtained from Lemma 4.14 in the case of
$(1/2,1/4,C_{q})$-intersecting sets.

Base Case ($|G|=1$): In this case, the lemma follows trivially.

Induction Step: Let $h\in G$ be an element of order $q$ in $G$ (the existence
of such an element is guaranteed by Cauchy’s Theorem for finite Abelian
groups121212Cauchy’s theorem states that in a finite Abelian group $G$ where
$|G|$ is divisible by a prime $p$, there exists an element of order $p$.), and
let $H=\langle h\rangle$ denote the subgroup generated by $h$.

Let $f^{\prime}:\\{0,1\\}^{n}\rightarrow G/H$ defined by

$f^{\prime}(\mathbf{x})=f(\mathbf{x})\pmod{H}$

Let $\\{P_{1},\ldots,P_{t}\\}$ be the set of linear polynomials in
$\mathcal{P}_{1}(\\{0,1\\}^{n},G/H)$ that are $1/2$-close to $f^{\prime}$.
Assuming that $\delta(P_{i},f^{\prime})=\frac{1}{2}-\beta_{i},$ we have by the
induction hypothesis

$\sum_{i=1}^{t}\beta_{i}^{D}\leq 1.$ (16)

We now consider the polynomials in $\mathcal{P}_{1}(\\{0,1\\}^{n},G)$ that are
$1/2$-close to $f.$ Given such a polynomial $Q$, we say that $Q$ _extends_
$P_{i}$ if $P_{i}=Q\pmod{H}$. Each such $Q$ extends a _unique_ $P_{i}$
($i\in[t]$).

Fix $P_{i}$ and assume that $Q_{1},\ldots,Q_{\ell}$ are the polynomials in
$\mathcal{P}_{1}(\\{0,1\\}^{n},G)$ that are $1/2$-close to $f$ and extend
$P_{i}.$ Assuming that $\delta(f,Q_{j})=\frac{1}{2}-\alpha_{j}$, we show that

$\sum_{j=1}^{\ell}\alpha_{j}^{D}\leq\beta_{i}^{D}.$ (17)

Assuming Equation 17, we sum over all $i\in[t]$, and then using Equation 16,
we get the inductive statement.

So it suffices to prove Equation 17, and we will do this using properties of
special intersection sets, in particular, Lemma 4.14. Fix $P_{i}$ and
$Q_{1},\ldots,Q_{\ell}$ as above for the rest of the proof.

Let $S$ denote the agreement set of $P_{i}$ and $f^{\prime}$, i.e.

$\displaystyle
S:=\left\\{\mathbf{x}\in\\{0,1\\}^{n}\;\middle|\;P_{i}(\mathbf{x})=f^{\prime}(\mathbf{x})\right\\},$

where $\mu(S)=(1/2+\beta_{i})$. Similarly, let $S_{j}$ ($j\in[\ell]$) denote
the agreement set of $Q_{j}$ and $f$, where $\mu(S)=(1/2+\alpha_{j})$. Note
that for every $j\in[\ell]$, $S_{j}\subseteq S$ since $Q_{j}$ extends $P_{i}$,
which implies that $\cup_{j\in[\ell]}S_{j}\subseteq S$.

The core for the proof of Equation 17 is to show that the sets
$S_{1},\ldots,S_{\ell}$ form a special intersecting set family inside the
universe $X=\\{0,1\\}^{n}$. We then use Lemma 4.14, and we upper bound the
number of extensions. In particular, we prove the following claim.

######  Claim 4.19 (Agreement sets are special intersecting sets).

The sets $S_{1},\ldots,S_{\ell}$ as defined above form a
$(1/2,1/4,C_{q})$-special intersecting sets, where $C_{q}$ is the constant
from Lemma 4.15.

Once we prove 4.19, we can then apply Lemma 4.14 on the sets
$S_{1},\ldots,S_{\ell}$. Using the observation that
$\cup_{j\in[\ell]}S_{j}\subseteq S$, we immediately get Equation 17, which
finishes the proof of Lemma 4.18. ∎

###### Proof of 4.19.

We verify the four properties from the definition of special intersecting
sets.

  1. 1.

For each $i\in[\ell]$, $\mu(S_{i})\geq 1/2$. This is true since each $Q_{i}$
is $1/2$-close to $f.$

  2. 2.

For any two distinct $i,j\in[\ell]$, $\mu(S_{i},S_{j})\leq 1/2$. This follows
from the Schwartz-Zippel Lemma (Theorem 2.1).

  3. 3.

Note that $H=\\{0,h,\ldots,(q-1)h\\}.$ We choose a set of coset
representatives $c_{1},\ldots,c_{M}$ ($M=|G|/|H|$) for $H$ in $G$. Now, given
any $g\in G,$ we can write it uniquely as $c_{p}+s\cdot h$ where $p\in[M]$ and
$s\in\\{0,\ldots,q-1\\}.$

In particular, using this decomposition at each input
$\mathbf{x}\in\\{0,1\\}^{n}$, we can write

$f(\mathbf{x})=\tilde{f}(\mathbf{x})+f^{\prime}(\mathbf{x})\cdot h$

where $\tilde{f}(\mathbf{x})$ is a coset representative and
$f^{\prime}(\mathbf{x})\in\\{0,1,\ldots,q-1\\}$ which we identify with
$\mathbb{Z}_{q}.$

Similarly, given an polynomial
$Q(\mathbf{x})=a_{0}+\sum_{k=1}^{n}a_{k}x_{k}\in\mathcal{P}_{1}(\\{0,1\\}^{n},G)$,
we apply the above decomposition to each of its coefficients to write

$Q(\mathbf{x})=\underbrace{\left(c_{p_{0}}+\sum_{i=1}^{n}c_{p_{i}}x_{i}\right)}_{\tilde{Q}(\mathbf{x})}+\underbrace{\left(s_{0}+\sum_{i=1}^{n}s_{i}x_{i}\right)}_{Q^{\prime}(\mathbf{x})}\cdot
h$

We treat the polynomial $Q^{\prime}(\mathbf{x})$ as a polynomial over the
group $\mathbb{Z}_{q}$. (This makes sense as the order of $h$ is $q$.)

Returning to the polynomials $Q_{1},\ldots,Q_{\ell}$, we note that if
$Q_{j}(\mathbf{x})=f(\mathbf{x}),$ then it must be true that
$Q_{j}^{\prime}(\mathbf{x})=f^{\prime}(\mathbf{x})$, implying that each
$S_{j}$ is contained in $S_{j}^{\prime}:=\\{\mathbf{x}\in\\{0,1\\}^{n}\ |\
Q_{j}^{\prime}(\mathbf{x})=f^{\prime}(\mathbf{x})\\}$. If we assume that
$|S_{j}^{\prime}|=\frac{1}{2}+\alpha_{j}^{\prime}$, then we have

$\sum_{j=1}^{\ell}\alpha_{j}^{C_{q}}\leq\sum_{j=1}^{\ell}(\alpha_{j}^{\prime})^{C_{q}}\leq
1$

where the final inequality is the extended Johnson bound (Lemma 4.15).

  4. 4.

Let $I\subseteq[\ell]$ be a subset with $|I|\geq 3$ such that
$\mu(S_{I})>1/4$. Let $T_{I}$ denote the following set

$\displaystyle
T_{I}=\left\\{\mathbf{x}\in\\{0,1\\}^{n}\;\middle|\;Q_{j}(\mathbf{x})=Q_{k}(\mathbf{x})\
\forall j,k\in I\right\\}$

Observe that $S_{I}\subseteq T_{I}$, and hence we have $\mu(T_{I})>1/4$.

We now note that the polynomials $Q_{1},\ldots,Q_{\ell}$ are all equal modulo
$H,$ implying that $\tilde{Q}_{1}=\cdots=\tilde{Q}_{\ell}.$ In particular, we
see that for $j\neq k\in I,$

$Q_{j}(\mathbf{x})=Q_{k}(\mathbf{x})\Longleftrightarrow
Q_{j}^{\prime}(\mathbf{x})=Q_{k}^{\prime}(\mathbf{x})$

where the latter equality is an equality of polynomials over $\mathbb{Z}_{q}.$
In other words, $T_{I}$ is the solution set in $\\{0,1\\}^{n}$ to the
following system of linear equations over $\mathbb{Z}_{q}$:

$\displaystyle
Q^{\prime}_{jk}(\mathbf{x}):=Q_{j}^{\prime}(\mathbf{x})-Q_{k}^{\prime}(\mathbf{x})=0,\quad\text{
for all }\ j,k\in I.$

Applying 4.20, we see that the set of polynomials
$\left\\{Q^{\prime}_{jk}\;\middle|\;j,k\in I\right\\}$ are all integer
multiples of a single linear polynomial. Call this polynomial $R(\mathbf{x})$.

We are now ready to prove property 4. Fix any $J=\\{j,k\\}\subseteq I$. If
$\mathbf{x}\in S_{J},$ then $Q^{\prime}_{jk}(\mathbf{x})=0$, implying that
$R(\mathbf{x})=0.$ This implies that all the polynomials $Q_{r}$ ($r\in I$)
take the same value at this point $\mathbf{x}.$ Moreover, since $\mathbf{x}\in
S_{J}$, we have $Q_{j}(\mathbf{x})=f(\mathbf{x})$, implying that
$Q_{r}(\mathbf{x})=f(\mathbf{x})$ for each $r\in I.$ This shows that
$S_{J}\subseteq S_{I}.$ Since $S_{I}\subseteq S_{J}$ trivially, we have
$S_{I}=S_{J}$ and we have thus shown property 4.

This shows that $S_{1},\ldots,S_{\ell}$ form a $(1/2,1/4,C_{q})$-special
intersecting sets. ∎

Now all that remains is to prove the following claim.

######  Claim 4.20 (Dimension of system of linear equations).

Let $q$ be a prime and let $\left\\{L_{i}(\mathbf{x})=0\right\\}_{i=1}^{m}$ be
a set of linear constraints over $\mathbb{Z}_{q}$. If the fraction of
solutions of this set in $\\{0,1\\}^{n}$ is $>1/2^{r}$ i.e.

$\displaystyle|\left\\{\mathbf{x}\in\\{0,1\\}^{n}\;\middle|\;L_{i}(\mathbf{x})=0,\text{
for all }\;i\in[m]\right\\}|>\dfrac{1}{2^{r}}\cdot 2^{n},$

then the dimension131313Since $q$ is prime, we can measure the dimension of
this set in the standard linear-algebraic sense. of
$\left\\{L_{i}(\mathbf{x})\right\\}_{i=1}^{m}$ is $<r$.

###### Proof.

Suppose $\dim\left(\left\\{L_{i}(\mathbf{x})\right\\}_{i=1}^{m}\right)=r$. Let
$M\in\mathbb{Z}_{q}^{m\times n}$ denote the coefficient matrix of the above
system of equations, i.e. the $i^{th}$ row of $M$ denotes the coefficients of
the variables in $L_{i}(\mathbf{x})$. Since the dimension is $r$, we know that
$\dim(M)$ is either $r-1$ or $r$.

If $\dim(M)=r-1$, then the system of equations $L_{i}(\mathbf{x})=0$
($i\in[m]$) has no solution, implying that the claim is trivially true. So we
assume that $\dim(M)=r.$

By doing elementary row operations, we can assume without loss of generality
that the top leftmost $r\times r$ sub-matrix of $M$ is the $r$-dimensional
identity matrix $I_{r}$. Let the new linear polynomials (after the elementary
row transformations) be $L_{1}^{\prime},\ldots,L_{m}^{\prime}$. We then have
the following property: For $i\in[r]$, $x_{i}\in\mathrm{vars}(L_{i}^{\prime})$
and $x_{i}\notin\mathrm{vars}(L_{j}^{\prime})$ for all $j\in[r]$ and $j\neq
i$.

Now for any assignment of $x_{r+1},\ldots,x_{n}\in\\{0,1\\}^{n-r}$, there
exists at most one assignment of $x_{1},\ldots,x_{r}\in\\{0,1\\}^{r}$ that
satisfies the constraints. Thus the number of solutions in $\\{0,1\\}^{n}$ is
at most $2^{n-r}$. The claim follows. ∎

##  5 Local List Correction Algorithm

In this section, we prove Theorem 1.3, i.e. we construct a local list
correction algorithm for $\mathcal{P}_{1}$. Our algorithm first constructs a
list of deterministic oracles that are close to the polynomials in the list
and then uses our local correction algorithm (see Theorem 1.1) on those
oracles.

Let $G$ be an Abelian group. Let $f:\\{0,1\\}^{n}\to G$ be any function. Let
$\mathsf{List}_{\varepsilon}^{f}$ denote the set of degree $1$ polynomials
that are $(1/2-\varepsilon)$-close to $f$, and let
$L(\varepsilon)=|\mathsf{List}_{\varepsilon}^{f}|$. Recall from Theorem 1.2
that
$L(\varepsilon)=\mathop{\mathrm{poly}}(1/\varepsilon)=\mathcal{O}_{\varepsilon}(1).$

We state the main construction of our local list-correction algorithm.

######  Theorem 5.1 (Approximating oracles).

Fix $n\in\mathbb{N}$ and $\varepsilon>0$. There exists an algorithm
$\mathcal{A}_{1}^{f}$ that makes at most $\mathcal{O}_{\varepsilon}(1)$ oracle
queries and outputs deterministic algorithms
$\psi_{1},\ldots,\psi_{L^{\prime}}$ satisfying the following property: with
probability at least $3/4$, for every polynomial
$P\in\mathsf{List}_{\varepsilon}^{f}$, there exists a $j\in[L^{\prime}]$ such
that $\delta(\psi_{j},P)\leq 1/100$, and moreover, for every
$\mathbf{x}\in\\{0,1\\}^{n}$, $\psi_{j}$ computes $P(\mathbf{x})$ by making at
most $\mathcal{O}_{\varepsilon}(1)$ oracle queries to $f$. Here
$L^{\prime}=\mathcal{O}(L(\varepsilon/2)\log
L(\varepsilon/2))=\mathcal{O}_{\varepsilon}(1)$.

Let us first see why the construction of approximating oracles is enough to
prove Theorem 1.3.

###### Proof of Theorem 1.3.

We first run the algorithm given by Theorem 5.1 and it outputs
$\psi_{1},\ldots,\psi_{L^{\prime}}$. Next we run our local correction
algorithm for $\mathcal{P}_{1}$ (see Theorem 1.1 and Section 3) with
$\psi_{1},\ldots,\psi_{L^{\prime}}$ as oracles, and these algorithms will be
$\phi_{1},\ldots,\phi_{L^{\prime}}$. This completes the description of the
local list correction algorithm $\mathcal{A}^{f}$ for $\mathcal{P}_{1}$, and
the bound on correctness probability follows from the correctness probability
of Theorem 1.1 and Theorem 5.1.
The algorithm $\mathcal{A}_{1}$ makes $\mathcal{O}_{\varepsilon}(1)$ queries
to $f$ as stated in Theorem 5.1, and then each $\phi_{i}$ makes
$\mathcal{O}_{\varepsilon}(1)\cdot\tilde{\mathcal{O}}(\log
n)=\tilde{\mathcal{O}}_{\varepsilon}(\log n)$ queries to $f$. ∎

In the rest of the section, we prove Theorem 5.1.

###  5.1 Overview of the Algorithms

In this section, we give a bird’s-eye view of the algorithms $\mathcal{A}_{1}$
and $\psi_{1},\ldots,\psi_{L^{\prime}}$. As discussed in the proof overview,
our algorithm is inspired by the list decoding algorithm for multivariate low-
degree polynomials of [STV01]. We expand the discussion from the proof
overview below. To use the same notation from the proof overview, let
$S:=\mathsf{List}_{\varepsilon}^{f}$.

  1. 1.

Getting the advice : This is a pre-processing step for the local list
correction algorithm. The algorithm $\mathcal{A}_{1}^{f}$ queries $f$ on a
random subcube $\mathsf{C}$ (see Definition 5) of dimension
$k=\mathcal{O}_{\varepsilon}(1)$. $\mathcal{A}_{1}^{f}$ will query on all of
$\mathsf{C}$ and return all degree $d$ polynomials that are almost
$(1/2-\varepsilon)$-close to $f$ on $\mathsf{C}$. Denote the set of
polynomials by $\tilde{S}:=\left\\{Q_{1},\ldots,Q_{L^{\prime}}\right\\}$.
Using a consequence of hypercontractivity and Chebyshev’s inequality (see
Lemma 2.4), we will show that for any $P\in\mathsf{List}_{\varepsilon}^{f}$,
with high probability (over the randomness of $\mathsf{C}$), there exists a
$j\in[L^{\prime}]$ such that $P|_{\mathsf{C}}=Q_{j}$. Then $\psi_{j}$ will use
$Q_{j}$ as advice. The details are described in Algorithm 3.

  2. 2.

The algorithm $\psi_{j}$ works as follows.

    1. (a)

Computing a list of values: For any input $\mathbf{b}$, $\psi_{j}$ will
construct a subcube $\mathsf{C^{\prime}}$ of dimension $2k$ containing
$\mathsf{C}$ and $\mathbf{b}$. $\psi_{j}$ will query $f$ on
$\mathsf{C^{\prime}}$ and find all polynomials that are almost
$(1/2-\varepsilon/2)$-close to $f$ on $\mathsf{C^{\prime}}$. Denote the set of
polynomials by $S^{\prime}:=\left\\{R_{1},\ldots,R_{L^{\prime}}\right\\}$.
When the input $\mathbf{b}$ is random, we can show as in the previous step
that, with high probability, for any $P\in\mathsf{List}_{\varepsilon}^{f}$,
there exists a $i\in[L^{\prime}]$ such that $P|_{\mathsf{C^{\prime}}}=R_{i}$.

    2. (b)

Filtering the correct value using the advice: $\psi_{j}$ has a list of
polynomials $S^{\prime}$, and it has to decide which of the polynomials in $S$
is equal to the restriction $P|_{\mathsf{C^{\prime}}}$. To find this
polynomial, $\psi_{j}$ will use the advice from Step 1 and check which of the
polynomials from Step 2 is equal to the advice. Having found the correct
polynomial $R_{j}$, the algorithm outputs the value of $R_{j}$ at the point
$\mathbf{b}.$ The details of $\psi_{j}$ are described in Algorithm 2.

There is a subtlety here: To check whether a polynomial from $S^{\prime}$ is
equal to the advice or not, $\psi_{j}$ will restrict the polynomials in
$S^{\prime}$ to $\mathsf{C}$. Because of the underlying random process, this
involves partitioning the variables $y_{1},\ldots,y_{2k}$ uniformly and
randomly into pairs and identifying them. Under this random pairing, a
polynomial $R_{j^{\prime}}\in S^{\prime}$ which is not equal to
$P|_{\mathsf{C^{\prime}}}$ may become equal to the advice. We will carefully
upper bound the probability of this event in most cases by a combinatorial
argument. The only bad case for this argument is when the difference
polynomial $D:=R_{j^{\prime}}-P|_{\mathsf{C}^{\prime}}$ is of the form
$\alpha\cdot(y_{1}+\cdots+y_{2k})$ where $\alpha\in G$ is an element of order
$2.$ By setting $k$ to be even, we ensure that in this case $R_{j^{\prime}}$
and $P|_{\mathsf{C}^{\prime}}$ evaluate to the same value at $\mathbf{b}$ and
hence it does not matter which of the polynomials is chosen to obtain the
final output.

Before we describe our algorithms, we need to describe a sub-routine - given
an embedding of a subcube $\mathsf{C}$ and a point $\mathbf{b}$, we would like
to find a small random subcube $\mathsf{C}^{\prime}$ such that $\mathsf{C}$ is
contained in $\mathsf{C}^{\prime}$ and $\mathsf{C}^{\prime}$ also contains
$\mathbf{b}$.

######  Definition 9 (Subcube spanned by $\mathsf{C}$ and $\mathbf{a}$).

Let $\mathsf{C}=C_{\mathbf{a},h}$ be an embedding of a subcube of dimension
$k$ (see Definition 5). For any point $\mathbf{b}\in\\{0,1\\}^{n}$, let
$\mathbf{v}:=\mathbf{a}\oplus\mathbf{b}$. Pick a uniformly random permutation
$\sigma:[2k]\rightarrow[2k]$. Define a hash function $h^{\prime}:[n]\to[2k]$
as follows: For all $i\in[n]$,

$\displaystyle h^{\prime}(i)=\begin{cases}\sigma(j),&\text{if
}\,h(i)=j\,\text{ and }\,v_{i}=0\\\ \sigma(j+k),&\text{if }\,h(i)=j\,\text{
and }\,v_{i}=1.\end{cases}$

In other words, the partition of $[n]$ given by $h^{\prime}$ is a refinement
of the partition given by $h$, where the refinement depends on whether
$\mathbf{b}$ and $\mathbf{a}$ agree on a coordinate.
For every $\mathbf{z}\in\\{0,1\\}^{2k}$, $x(\mathbf{z})$ is defined as
follows:

$\displaystyle x(\mathbf{z})_{i}=z_{h^{\prime}(i)}\oplus a_{i}.$

$\mathsf{C}^{\mathbf{b}}$ is the set of points $x(\mathbf{z})$ for all
$\mathbf{z}\in\\{0,1\\}^{2k}$, i.e.
$\mathsf{C}^{\mathbf{b}}:=\left\\{x(\mathbf{z})\;\middle|\;\mathbf{z}\in\\{0,1\\}^{2k}\right\\}$.

It is easy to verify from the definition that
$\mathsf{C}\subset\mathsf{C}^{\mathbf{b}}$, and also
$\mathbf{b}\in\mathsf{C}^{\mathbf{b}}$. In particular, say we define
$\mathbf{w}\in\\{0,1\\}^{2k}$ as follows: for $j\in[k]$, $w_{\sigma(j)}=0$ and
$w_{\sigma(j+k)}=1$. Then $x(\mathbf{w})=\mathbf{b}$.

######  Observation 5.2.

Let $h$ be a random hash function from $[n]$ to $[k]$ and
$\mathbf{a}\sim\\{0,1\\}^{n}$. Then for a random
$\mathbf{b}\sim\\{0,1\\}^{n}$, $h^{\prime}$ as defined above is a random hash
function from $[n]$ to $[2k]$ \- this follows because for a random
$\mathbf{b}\sim\\{0,1\\}^{n}$, $\mathbf{v}$ is uniformly distributed in
$\\{0,1\\}^{n}$ and independent of $\mathbf{a}$. This means that
$\mathsf{C}^{\mathbf{b}}$ as defined above is a random embedding of a subcube
of dimension $2k$ (see Section 2 just after Definition 5).

Furthermore, conditioned on the choice of $\mathsf{C}^{\prime}$ (i.e. the
choice of $\mathbf{a},h^{\prime}$), the subcube $\mathsf{C}$ may be described
as follows: we partition the variables $z_{1},\ldots,z_{2k}$ into pairs
uniformly at random and identify the variables in each pair.

Finally, note that $\mathbf{b}=x(\mathbf{w})$ for some $\mathbf{w}$ of Hamming
weight exactly $k$.

###  5.2 The Algorithms

Let $\mathsf{C}$ be a subcube of dimension $k$ and $Q:\\{0,1\\}^{k}\to G$ a
degree-$1$ polynomial, which we consider to be a function on $\mathsf{C}$. We
will use $\psi_{\mathsf{C},\sigma,Q}$ to denote a _deterministic_ algorithm
that has the description of $\mathsf{C}$, a permutation
$\sigma:[2k]\rightarrow[2k],$ and evaluation of $Q$ on $\mathsf{C}$ hardwired
inside it141414In the final algorithm, $\mathsf{C}$ will be a random subcube
of dimension $\mathrm{poly}(1/\varepsilon)$ and $Q$ with high probability be
equal to $P|_{\mathsf{C}}$, for some $P\in\mathsf{List}_{\varepsilon}^{f}$.
The description of algorithm $\psi_{\mathsf{C},\sigma,Q}$ follows.

1 Input: Oracle access to $f$, $\mathbf{b}\in\\{0,1\\}^{n}$ 2 3Let
$\mathsf{C}^{\prime}$ be a bigger subcube containing $\mathsf{C}$ and
$\mathbf{b}$ constructed using $\sigma$ as in Definition 9 Let
$\mathbf{w}\in\\{0,1\\}^{2k}$ such that $x(\mathbf{w})=\mathbf{b}$ //
$|\mathbf{w}|=k$ Query $f$ on $\mathsf{C}^{\prime}$ // Number of queries is
$2^{2k}$ Use the algorithm in Theorem A.2 to find all polynomials
$R_{1},\ldots,R_{L^{\prime\prime}}\in\mathcal{P}_{1}(\\{0,1\\}^{2k},G)$ that
are $\left(\frac{1}{2}-\frac{\varepsilon}{2}\right)$-close to
$f|_{\mathsf{C^{\prime}}}$ // $L^{\prime\prime}\leq L(\varepsilon/2)$ 4 if
_there exists an $i\in[L^{\prime\prime}]$ such that $R_{i}|_{\mathsf{C}}=Q$_
then 5 pick any such $i$ and return _$R_{i}(\mathbf{w})$_ 6else return _$0$_
// An arbitrary value 7 8 Algorithm 2 Approximating algorithm
$\psi_{\mathsf{C},\sigma,Q}$

Now we can state the algorithm $\mathcal{A}_{1}$.

1 Input: Oracle access to $f$ 2 Choose $k\leftarrow 2\cdot
L(\varepsilon/2)^{3}\cdot\lceil 1/\varepsilon^{5}\rceil$ // $k$ is even (will
be crucial later) 3 Set $\ell\leftarrow\log L(\varepsilon)$ 4
$T\leftarrow\emptyset$ 5 repeat 6 Sample random $\mathbf{a}\sim U_{n}$ and $h$
as a random hash function from $[n]$ to $[k]$ 7 Construct the subcube
$\mathsf{C}:=C_{\mathbf{a},h}$ according to Definition 5 Query $f$ on
$\mathsf{C}$ // Number of queries is $2^{k}$ Use the algorithm in Theorem A.2
to find all polynomials
$Q_{1},\ldots,Q_{L^{\prime}}\in\mathcal{P}_{1}(\\{0,1\\}^{k},G)$ that are
$\left(\frac{1}{2}-\frac{\varepsilon}{2}\right)$-close to $f|_{\mathsf{C}}$ //
$L^{\prime}\leq L(\varepsilon/2)$ 8 $T\leftarrow
T\cup\left\\{Q_{1},\ldots,Q_{L^{\prime}}\right\\}$ 9until  _$\ell$ times_
10Pick a uniformly random permutation $\sigma:[2k]\rightarrow[2k]$ 11 return
_$\psi_{\mathsf{C},\sigma,Q_{1}},\ldots,\psi_{\mathsf{C},\sigma,Q_{t}}$ for
all $Q_{i}\in T$_ Algorithm 3 Algorithm $\mathcal{A}_{1}$

###  5.3 Analysis of the Algorithms

In this section, we will prove Theorem 5.1 by analyzing the query complexity
and the error probability.

##### Query complexity:

The algorithm $\mathcal{A}_{1}$ makes $2^{k}=\mathcal{O}_{\varepsilon}(1)$
queries to $f$ to output approximating oracles $\psi_{1},\ldots,\psi_{t}$.
Each approximating oracle $\psi_{i}$ makes
$2^{2k}=\mathcal{O}_{\varepsilon}(1)$ queries to return the evaluation at a
point $\mathbf{b}$.

##### Correctness:

We want to show that with probability $\geq 3/4$, for every
$P\in\mathsf{List}_{\varepsilon}^{f}$, there exists an oracle
$\psi_{\mathsf{C},\sigma,Q_{j}}$ such that
$\delta(\psi_{\mathsf{C},\sigma,Q_{j}},P)\leq 1/100$. We first show that in a
single iteration for Algorithm 3 the following holds: for every polynomial
$P\in\mathsf{List}_{\varepsilon}^{f}$, with probability at least $9/10$, there
exists a $1/100$-close approximating oracle $\psi_{j}$. We prove this is in
Lemma 5.3. Since we repeat this $\ell$ times, the probability that there is no
$1/100$-close approximating oracle for $P$ is at most $1/10^{\ell}$. By a
union bound for all polynomials $P\in\mathsf{List}_{\varepsilon}^{f}$, we get
the desired correctness probability in Theorem 5.1. Since each iteration
produces a list of size at most $L(\varepsilon/2),$ overall we obtain a list
of size $\mathcal{O}(L(\varepsilon/2)\cdot\log L(\varepsilon))$ as claimed.

######  Lemma 5.3 (Correctness of Local List Correction).

Fix any polynomial $P\in\mathsf{List}_{\varepsilon}^{f}$. Then the probability
(over the randomness of Algorithm 3) that there does not exist a $j$ such that
$\delta(\psi_{\mathsf{C},\sigma,Q_{j}},P)\leq 1/100$ is at most $1/10$.

###### Proof.

Let $\mathcal{E}_{P}$ denote the event that there does not exist a $j$ such
that $\delta(\psi_{\mathsf{C},\sigma,Q_{j}},P)\leq 1/100$. We want to bound
the probability of event $\mathcal{E}_{P}.$ We will show that

$\operatorname*{\mathbb{E}}_{\mathbf{a},h,\sigma}[\min_{j}\delta(\psi_{\mathsf{C},\sigma,Q_{j}},P)]=\operatorname*{\mathbb{E}}_{\mathbf{a},h,\sigma}[\min_{j}\Pr_{\mathbf{b}}[\psi_{\mathsf{C},\sigma,Q_{j}}(\mathbf{b})\neq
P(\mathbf{b})]]\leq 1/1000$ (18)

from which the lemma follows via an application of Markov’s inequality.

Define the following auxiliary events, depending on the choice of
$\mathbf{a},h$ and $\sigma$, along with the choice of a random input
$\mathbf{b}.$

  1. 1.

Event $\mathcal{E}_{1,P}$ (only depends on $\mathbf{a},h$): In Algorithm 3,
there does not exist a polynomial $Q_{j}$ such that $Q_{j}=P|_{\mathsf{C}}$.

  2. 2.

Event $\mathcal{E}_{2,P}$: In Algorithm 2, there does not exist a polynomial
$R_{i}$ such that $R_{i}=P|_{\mathsf{C^{\prime}}}$.

  3. 3.

Event $\mathcal{E}_{3,P}$: In Algorithm 2, there exist two polynomials
$R_{i_{1}}$ and $R_{i_{2}}$ such that $R_{i_{1}}(\mathbf{w})\neq
R_{i_{2}}(\mathbf{w})$ but $R_{i_{1}}|_{\mathsf{C}}=R_{i_{2}}|_{\mathsf{C}}$.
Here $\mathbf{w}$ is, as defined in Algorithm 2, the point in $\\{0,1\\}^{2k}$
of Hamming weight $k$ such that $x(\mathbf{w})=\mathbf{b}.$

To see how these events are useful in analyzing Equation 18, we proceed as
follows. For $\mathbf{a},h$ such that the event $\mathcal{E}_{1,P}$ does not
occur, we can fix a $j^{*}\leq L^{\prime}$ such that
$P|_{\mathsf{C}}=Q_{j^{*}}.$ Thus, we have

$\operatorname*{\mathbb{E}}_{\mathbf{a},h,\sigma}[\min_{j}\Pr_{\mathbf{b}}[\psi_{\mathsf{C},\sigma,Q_{j}}(\mathbf{b})\neq
P(\mathbf{b})]\leq\Pr_{\mathbf{a},h}[\mathcal{E}_{1,P}]+\operatorname*{\mathbb{E}}_{\mathbf{a},h,\sigma}[\mathbf{1}_{\neg\mathcal{E}_{1,P}}\cdot\Pr_{\mathbf{b}}[\psi_{\mathsf{C},\sigma,Q_{j^{*}}}(\mathbf{b})\neq
P(\mathbf{b})]]$ (19)

Fix any $\mathbf{a},h$ such that the event $\mathcal{E}_{1,P}$ does not occur.
Further, if the event $\mathcal{E}_{2,P}$ does not occur, then there is an
$i^{*}\leq L^{\prime\prime}$ such that $P|_{\mathsf{C}^{\prime}}=R_{i^{*}}.$
In particular, $R_{i^{*}}|_{\mathsf{C}}=P|_{\mathsf{C}}=Q_{j^{*}}.$

Finally, if event $\mathcal{E}_{3,P}$ also does not occur, then there is no
$i\neq i^{*}$ such that $R_{i^{*}}(\mathbf{w})\neq R_{i}(\mathbf{w})$ but
$R_{i}|_{\mathsf{C}}=R_{i^{*}}|_{\mathsf{C}}.$ In particular, the only
possible output of the algorithm $\psi_{\mathsf{C},\sigma,Q_{j^{*}}}$ on input
$\mathbf{w}$ is $R_{i^{*}}(\mathbf{w})=P(x(\mathbf{w}))=P(\mathbf{b}).$

We have thus shown that

$\operatorname*{\mathbb{E}}_{\mathbf{a},h,\sigma}[\mathbf{1}_{\neg\mathcal{E}_{1,P}}\cdot\Pr_{\mathbf{b}}[\psi_{\mathsf{C},\sigma,Q_{j^{*}}}(\mathbf{b})\neq
P(\mathbf{b})]]\leq\Pr_{\mathbf{a},h,\sigma,\mathbf{b}}[\mathcal{E}_{2,P}\vee\mathcal{E}_{3,P}]\leq\Pr_{\mathbf{a},h,\sigma,\mathbf{b}}[\mathcal{E}_{2,P}]+\Pr_{\mathbf{a},h,\sigma,\mathbf{b}}[\mathcal{E}_{3,P}].$

Plugging the above into Equation 19, we get

$\operatorname*{\mathbb{E}}_{\mathbf{a},h,\sigma}[\min_{j}\Pr_{\mathbf{b}}[\psi_{\mathsf{C},\sigma,Q_{j}}(\mathbf{b})\neq
P(\mathbf{b})]\leq\Pr_{\mathbf{a},h}[\mathcal{E}_{1,P}]+\Pr_{\mathbf{a},h,\sigma,\mathbf{b}}[\mathcal{E}_{2,P}]+\Pr_{\mathbf{a},h,\sigma,\mathbf{b}}[\mathcal{E}_{3,P}].$
(20)

So it now suffices to bound the probabilities of the events
$\mathcal{E}_{1,P},\mathcal{E}_{2,P}$ and $\mathcal{E}_{3,P}$, which we do in
the following two claims.

######  Claim 5.4.

$\Pr_{\mathbf{a},h}[\mathcal{E}_{1,P}],\Pr_{\mathbf{a},h,\sigma,\mathbf{b}}[\mathcal{E}_{2,P}]\leq
1/10000.$

######  Claim 5.5.

$\Pr_{\mathbf{a},h,\sigma,\mathbf{b}}[\mathcal{E}_{3,P}]\leq 1/10000.$

Substituting the above bounds into Equation 20, we get Equation 18, implying
the statement of the lemma. So it suffices to prove 5.4 and 5.5.

###### Proof of 5.4.

Recall that $\delta(P,f)\leq(1/2-\varepsilon).$ Equivalently, the set of
points $T$ where $f$ and $P$ differ has density at most $(1/2-\varepsilon)$ in
$\\{0,1\\}^{n}.$ For a cube $\mathsf{C}$, the non-existence of $Q_{j}$ such
that $Q_{j}=P|_{\mathsf{C}}$ is equivalent to
$\delta(P|_{\mathsf{C}},f|_{\mathsf{C}})>(1/2-\varepsilon/2)$.

For a random subcube $\mathsf{C}$ with this distribution, using Lemma 2.4 for
$T$ as above, we get that for $k\geq 1/\varepsilon^{5}$,

$\displaystyle\Pr_{\mathsf{C}}\left[\delta(P|_{\mathsf{C}},f|_{\mathsf{C}})>\frac{1}{2}-\frac{\varepsilon}{2}\right]\leq
1/10000.$

(Here, we are assuming, without loss of generality that $\varepsilon$ is less
than or equal to a small enough constant so that any $k\geq 1/\varepsilon^{5}$
satisfies the hypothesis of Lemma 2.4.) Hence $\Pr[\mathcal{E}_{1,P}]\leq
1/10000$.

Using 5.2, we know that $\mathsf{C^{\prime}}$ is also a random subcube of
dimension $2k$ (drawn from a similar distribution). Proceeding as above, we
get the stated upper bound on $\Pr[\mathcal{E}_{2,P}]$. ∎

###### Proof of 5.5.

To bound this probability, we first note that the polynomials
$R_{1},\ldots,R_{L^{\prime\prime}}$ are determined by the subcube
$\mathsf{C}^{\prime}.$ We condition on a fixed choice of
$\mathsf{C}^{\prime}.$ Recall that, as noted in 5.2, the subcube $\mathsf{C}$
is obtained from $\mathsf{C}^{\prime}$ by partitioning the $2k$ variables in
$\mathsf{C}^{\prime}$ into $k$ pairs uniformly at random and identifying the
variables in each pair.

We denote by $y_{1},\ldots,y_{2k}$ the variables of a polynomial $R$ defined
on $\mathsf{C}^{\prime}.$

Fix any pair of degree-$1$ polynomials $R_{i_{1}}$ and $R_{i_{2}}$ that are
found in Algorithm 2 such that $R_{i_{1}}(\mathbf{w})\neq
R_{i_{2}}(\mathbf{w}).$ Let $D_{i_{1},i_{2}}=R_{i_{1}}-R_{i_{2}}$, which
evaluates to a non-zero value at the point $\mathbf{w}.$ We consider the event
$D_{i_{1},i_{2}}|_{\mathsf{C}}=0.$ We will show that

$\Pr[D_{i_{1},i_{2}}|_{\mathsf{C}}=0]\leq\frac{\log k}{k}.$ (21)

Assuming the above, we can use a union bound over all pairs
$i_{1},i_{2}\in[L^{\prime\prime}]$ such that $R_{i_{1}}(\mathbf{w})\neq
R_{i_{2}}(\mathbf{w})$ to get

$\mathop{\mathrm{Pr}}[\mathcal{E}_{3,P}]\leq(L^{\prime\prime})^{2}\cdot\frac{\log
k}{k}\leq L(\varepsilon/2)^{2}\cdot\frac{\log k}{k}\leq\frac{1}{10000}$

where the last inequality follows from our choice of $k$ (we assume without
loss of generality that $\varepsilon$ is less than a small enough absolute
constant). This shows that Equation 21 implies the claim.

We now show Equation 21. Assume that

$\displaystyle
D_{i_{1},i_{2}}(y_{1},\ldots,y_{2k})=\alpha_{0}+\sum_{i=1}^{2k}\alpha_{i}y_{i}$

where $\alpha_{0},\ldots,\alpha_{2k}\in G.$

If $\alpha_{0}\neq 0$, then clearly $D_{i_{1},i_{2}}|_{\mathsf{C}}\neq 0$
since pairing and identifying variables does not change the constant term. So
we can assume without loss of generality that $\alpha_{0}=0$.

Let $\alpha$ denote the plurality of the coefficients
$\alpha_{1},\ldots,\alpha_{2k}$ of $D_{i_{1},i_{2}}$ (breaking ties
arbitrarily). Let $W\subseteq[2k]$ index the subset of coefficients that are
$\alpha$, i.e. $W:=\left\\{j\in[2k]\;\middle|\;\alpha_{j}=\alpha\right\\}$. We
have the following two cases depending on the order of $\alpha$.

  1. 1.

$\alpha\neq-\alpha$: We have two further cases depending on the size of $W$.

     * •

$|W|\geq\log k$: Note that for the polynomial $D_{i_{1},i_{2}}|_{\mathsf{C}}$
to vanish, it must be the case that each of the variables indexed by $W$ is
mapped to a variable with coefficient $-\alpha\neq\alpha.$ Since $-\alpha$ is
_not_ the plurality, it follows that at most half the variables have
coefficient $-\alpha.$ Hence, we have

$\displaystyle\Pr[D_{i_{1},i_{2}}|_{\mathsf{C}}=0]$
$\displaystyle\leq\Pr[\forall\;j\in W:\ \text{$y_{j}$ is paired with a
variable with coefficient $-\alpha$}]$ $\displaystyle\leq(1/2)^{\log k}=1/k,$

which implies Equation 21 in this case.

     * •

$|W|<\log k$: Since $\alpha$ is the most frequently appearing coefficient,
this implies that no coefficient appears more than $\log k$ times.
Specifically, this also applies to $-\alpha$. Hence, for any $j\in W$, the
probability that $y_{j}$ is mapped to a variable with coefficient $-\alpha$ is
at most $(\log k)/k,$ implying Equation 21 in this case.

  2. 2.

$\alpha=-\alpha$ (i.e. $2\alpha=0$): We have two further sub-cases depending
on the size of $\overline{W}$, the complement of $W.$

     * •

$|\overline{W}|\geq\log k$: For the polynomial $D_{i_{1},i_{2}}|_{\mathsf{C}}$
to vanish, each variable indexed by a $j\in\overline{W}$ with coefficient
$\alpha_{j}\neq\alpha$ must be paired with another variable with coefficient
$-\alpha_{j}$. Since $\alpha_{j}\neq\alpha,$ we also see that
$-\alpha_{j}\neq\alpha$ and hence $-\alpha_{j}$ is the coefficient of at most
half the variables. Thus, we can upper bound the probability that
$D_{i_{1},i_{2}}|_{\mathsf{C}}$ vanishes as follows.

$\displaystyle\Pr_{\sigma}[\forall\;i\in\overline{W}\,:\text{$y_{j}$ is paired
with a variable with coefficient $-\alpha_{j}$}]\leq(1/2)^{\log k}=1/k.$

     * •

$|\overline{W}|<\log k$: In this case, we note that
$\overline{W}\neq\emptyset$, and the reason is as follows.
$D_{i_{1},i_{2}}(\mathbf{w})\neq 0$ by assumption. On the other hand, we know
that $|\mathbf{w}|=k$ and we have chosen $k$ to be even (see Algorithm 3).
Thus $\alpha\cdot(w_{1}+\cdots+w_{2k})=0$. Hence, we cannot have
$D_{i_{1},i_{2}}=\alpha\cdot(y_{1}+\cdots+y_{2k}).$ Thus, there must be some
variable $y_{j}$ whose coefficient is not $\alpha.$

Fix any such $j\in\overline{W}$. For the polynomial
$D_{i_{1},i_{2}}|_{\mathsf{C}}$ to vanish, the variable $y_{j}$ must be paired
with another variable with coefficient $-\alpha_{j}$, and any such variable is
also indexed by an element of $\overline{W}.$ Since $|\overline{W}|<\log k,$
the probability of this is at most $(\log k)/k,$ implying the claimed
probability bound.

We have thus shown Equation 21, implying the proof of the claim. ∎

As discussed above, we have proved 5.4 and 5.5 and substituting them in
Equation 20, we get the desired bound, and this concludes the correctness of
the local list correction algorithm. ∎

## References

  * [ASS23] Prashanth Amireddy, Srikanth Srinivasan, and Madhu Sudan.  Low-degree testing over grids.  In Approximation, Randomization, and Combinatorial Optimization (RANDOM), volume 275, pages 41:1–41:22, 2023.
  * [AVu97] Noga Alon and Văn H. Vũ.  Anti-hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs.  J. Comb. Theory Ser. A, 79(1):133–160, 1997.
  * [BDYW11] Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson.  Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes.  In ACM Symposium on Theory of Computing (STOC), pages 519–528, 2011.
  * [BF90] Donald Beaver and Joan Feigenbaum.  Hiding instances in multioracle queries.  In Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 415, pages 37–48, 1990.
  * [BHPS10] László Babai, Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii, and Xiaoming Sun.  Weights of exact threshold functions.  Izvestiya: Mathematics, 85:1039 – 1059, 2010.
  * [BL18] Abhishek Bhowmick and Shachar Lovett.  The list decoding radius for Reed-Muller codes over small fields.  IEEE Trans. Inf. Theory, 64(6):4382–4391, 2018.
  * [BSS20] Mitali Bafna, Srikanth Srinivasan, and Madhu Sudan.  Local decoding and testing of polynomials over grids.  Random Struct. Algorithms, 57(3):658–694, 2020.
  * [Con] Keith Conrad.  Characters of finite abelian groups.  https://kconrad.math.uconn.edu/blurbs/grouptheory/charthy.pdf.  Expository paper.
  * [DGKS08] Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan.  Decodability of group homomorphisms beyond the Johnson bound.  Electron. Colloquium Comput. Complex., TR08-020, 2008.
  * [DSW14] Zeev Dvir, Shubhangi Saraf, and Avi Wigderson.  Improved rank bounds for design matrices and a new proof of Kelly’s theorem.  Forum Math. Sigma, 2:Paper No. e4, 24, 2014.
  * [DSW17] Zeev Dvir, Shubhangi Saraf, and Avi Wigderson.  Superquadratic lower bound for 3-query locally correctable codes over the reals.  Theory Comput., 13:Paper No. 11, 36, 2017.
  * [Eli57] Peter Elias.  List decoding for noisy channels.  Technical Report 335, Research Laboratory of Electronics, MIT, 1957.
  * [GHR92] Mikael Goldmann, Johan Håstad, and Alexander A. Razborov.  Majority gates vs. general weighted threshold gates.  Computational Complexity, 2:277–300, 1992.
  * [GKS06] Elena Grigorescu, Swastik Kopparty, and Madhu Sudan.  Local decoding and testing for homomorphisms.  In International Workshop on Approximation Algorithms for Combinatorial Optimization (RANDOM), volume 4110, pages 375–385, 2006.
  * [GKZ08] Parikshit Gopalan, Adam R. Klivans, and David Zuckerman.  List-decoding Reed-Muller codes over small fields.  In ACM Symposium on Theory of Computing (STOC), pages 265–274, 2008.
  * [GL89] Oded Goldreich and Leonid A. Levin.  A hard-core predicate for all one-way functions.  In ACM Symposium on Theory of Computing (STOC), pages 25–32, 1989.
  * [GLR+91] Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson.  Self-testing/correcting for polynomials and for approximate functions.  In ACM Symposium on Theory of Computing (STOC), pages 32–42, 1991.
  * [GRS23] Venkatesan Guruswami, Atri Rudra, and Madhu Sudan.  Essential Coding Theory (Book draft).  2023\.
  * [GS92] Peter Gemmell and Madhu Sudan.  Highly resilient correctors for polynomials.  Inf. Process. Lett., 43(4):169–174, 1992.
  * [GS99] Venkatesan Guruswami and Madhu Sudan.  Improved decoding of Reed-Solomon and algebraic-geometry codes.  IEEE Trans. Inf. Theory, 45(6):1757–1767, 1999.
  * [H9̊4] Johan Håstad.  On the size of weights for threshold gates.  SIAM J. Discret. Math., 7(3):484–492, 1994.
  * [Juk11] Stasys Jukna.  Extremal combinatorics: with applications in computer science, volume 571.  Springer, 2011.
  * [KK17] John Y. Kim and Swastik Kopparty.  Decoding Reed-Muller codes over product sets.  Theory Comput., 13(1):1–38, 2017.
  * [KM93] Eyal Kushilevitz and Yishay Mansour.  Learning decision trees using the Fourier spectrum.  SIAM Journal on Computing, 22(6):1331–1348, 1993.
  * [Lip89] Richard J. Lipton.  New directions in testing.  In Distributed Computing And Cryptography, volume 2, pages 191–202, 1989.
  * [Man11] Yishay Mansour.  Lecture 5: Lower Bounds using Information Theory Tools.  http://www.math.tau.ac.il/~mansour/advanced-agt+ml/scribe5-lower-bound-MAB.pdf, 2011.  Lecture notes.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [Ore22] Øystein Ore.  Über höhere kongruenzen.  Norsk Mat. Forenings Skrifter, 1(7):15, 1922.
  * [Pod09] Vladimir V. Podolskii.  Perceptrons of large weight.  Probl. Inf. Transm., 45(1):46–53, 2009.
  * [Ree54] Irving S. Reed.  A class of multiple-error-correcting codes and the decoding scheme.  Trans. IRE Prof. Group Inf. Theory, 4:38–49, 1954.
  * [STV01] Madhu Sudan, Luca Trevisan, and Salil P. Vadhan.  Pseudorandom generators without the XOR lemma.  J. Comput. Syst. Sci., 62(2):236–266, 2001.
  * [Sud97] Madhu Sudan.  Decoding of reed solomon codes beyond the error-correction bound.  J. Complex., 13(1):180–193, 1997.

##  Appendix A Non-Local Algorithms for Decoding Low-Degree Polynomials

In this section, we prove the following results regarding unique and list
decoding algorithms for $\mathcal{P}_{d}$ over an arbitrary Abelian group $G.$
We assume throughout that group operations (addition, inverse etc.) and
comparing group elements can be done in constant time.

######  Theorem A.1 (essentially due to Reed [Ree54]).

Fix any Abelian group $G.$ There is a $\mathop{\mathrm{poly}}(2^{n})$-time
algorithm that, given oracle access to a function $f:\\{0,1\\}^{n}\rightarrow
G$ produces the unique polynomial $P\in\mathcal{P}_{d}$ such that
$\delta(f,P)<1/2^{d+1}$, assuming that such a $P$ exists.

######  Theorem A.2.

Fix any Abelian group $G$ and degree parameter $d.$ There is a
$\mathop{\mathrm{poly}}(2^{n^{d+1}})$-time algorithm that, given oracle access
to a function $f:\\{0,1\\}^{n}\rightarrow G$ produces a list of all
polynomials $P\in\mathcal{P}_{d}$ such that $\delta(f,P)<1/2^{d}$.

######  Remark A.3.

We will use Theorem A.2 in the setting for $d=1$ and output polynomials $P$
such that when $\delta(f,P)>(1/2-\varepsilon)$, for some $\varepsilon>0$. Our
algorithm will output a list $\mathcal{L}\subset\mathcal{P}_{1}$ of size
$2^{\mathcal{O}(n^{2})}$. $\mathcal{L}$ may contain polynomials that are not
$(1/2-\varepsilon)$-close to $f$ and we would prune $\mathcal{L}$ to remove
these polynomials. To do this, we simply compute $\delta(f,R)$ for every
$R\in\mathcal{L}$, and remove $R$ if $\delta(f,R)>(1/2-\varepsilon)$. This can
be done in time
$\mathcal{O}(2^{n}\cdot|\mathcal{L}|)=\mathcal{O}(2^{\mathcal{O}(n^{2})})$,
and this adds up to the time stated in Theorem A.2.

###  A.1 Proof Sketch of Theorem A.1

We only give a sketch here, because the algorithm and proof of correctness are
almost identical to the Majority-logic decoding algorithm of Reed [Ree54] (see
also [GRS23, Chapter 14]).

We need the following lemma, which follows immediately from Möbius Inversion
(item 1 in Theorem 2.1).

######  Lemma A.4.

Fix $P\in\mathcal{P}_{d}(\\{0,1\\}^{n},G)$ and $I\subseteq[n]$ of size $[d].$
Let $\mathbf{a}\in\\{0,1\\}^{n-d}$ be any assignment to the variables outside
$I.$ Then, the coefficient $c_{I}$ of $\prod_{i\in I}x_{i}$ in $P$ is given by

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

where $1_{J}\circ\mathbf{a}$ denotes the input $\mathbf{b}\in\\{0,1\\}^{n}$
that agrees with the indicator vector of $J$ on co-ordinates inside $I$ and
the fixed input $\mathbf{a}$ on co-ordinates outside $I.$

###### Proof.

This follows directly from item 1 of Theorem 2.1 applied to the restriction of
$P$ obtained by setting the variables outside $I$ according to the values
assigned by $\mathbf{a}.$ Note that this restriction does not change the
coefficient of the monomial $\prod_{i\in I}x_{i}$ (though it can change other
coefficients). Hence, the coefficient of the restricted polynomial is equal to
$c_{I}.$ ∎

We can now sketch Reed’s Majority-logic algorithm in this setting. Assume that
we are given $f$ such that $\delta(f,P)<1/2^{d+1}$. For each $I\subseteq[n]$
of size at most $d$, let $c_{I}$ denote the coefficient of the monomial
$\prod_{i\in I}x_{i}$ in $P.$

##### Finding $c_{I}$ for $|I|=d$.

Fix any $I$ of size $[d].$ For each setting $\mathbf{a}\in\\{0,1\\}^{n-d}$,
compute

$c_{I,\mathbf{a}}=\sum_{J\subseteq I}(-1)^{|I\setminus
J|}f(1_{J}\circ\mathbf{a})$ (23)

where $1_{J}\circ\mathbf{a}$ is as defined in the statement of Lemma A.4.
Among these $2^{n-d}$ many group elements, output the most commonly occurring
one.

##### Correctness.

Since $\delta(f,P)<1/2^{d+1},$ it follows that for strictly more than half the
possibilities for $\mathbf{a}\in\\{0,1\\}^{n-d},$ the function $f$ agrees with
$P$ on all inputs in the subcube $C_{\mathbf{a}}$ obtained by setting
variables outside $I$ according to $\mathbf{a}$ (not to be confused with the
kinds of subcubes defined in Definition 5). This implies that
$c_{I,\mathbf{a}}=c_{I}$ for all such $\mathbf{a}.$ Hence, the mostly commonly
occurring value among the $c_{I,\mathbf{a}}$ ($\mathbf{a}\in\\{0,1\\}^{n-d}$)
is the right coefficient $c_{I}$.

##### Recursion to find other coefficients.

After finding all the coefficients of monomials of degree $d,$ we replace the
function $f$ with $f^{\prime}$ where

$f^{\prime}(\mathbf{x})=f(\mathbf{x})-\sum_{|I|=d}c_{I}\prod_{i\in I}x_{i}.$

We then apply a recursive procedure to $f^{\prime}$ with $d$ replaced by
$d-1$.

##### Correctness.

Define analogously a $P^{\prime}\in\mathcal{P}_{d-1}(\\{0,1\\}^{n},G)$ by

$P^{\prime}(\mathbf{x})=P(\mathbf{x})-\sum_{|I|=d}c_{I}\prod_{i\in
I}x_{i}=\sum_{|I|<d}c_{I}\prod_{i\in I}x_{i}.$

Note that $\delta(f^{\prime},P^{\prime})=\delta(f,P)<1/2^{d+1}<1/2^{d}.$
Hence, by induction, the recursive procedure correctly finds $c_{I}$ for
$|I|<d.$

##### Running time.

The running time is easily analyzed to be $(d+1)\cdot 2^{O(n)}=2^{O(n)}.$

###  A.2 Proof Sketch of Theorem A.2

The algorithm is similar to the Majority-logic algorithm above, except that in
the first step, we now find a large list of polynomials.

Assume that we are given $f:\\{0,1\\}^{n}\rightarrow G$. Below, $P$ will
denote any degree $d$ polynomial such that $\delta(f,P)<1/2^{d}$. The
coefficients $c_{I}$ of $P$ are as defined in the previous section.

We describe the algorithm in analogy with the algorithm from the previous
section. The difference is that in the first step, we find a _list_ of
homogeneous polynomials of degree $d$ such that one of them is exactly the
homogeneous component of the polynomial $P.$

##### Finding $c_{I}$ for $|I|=d$.

For $I$ of size $d$ and $\mathbf{a}\in\\{0,1\\}^{n-d}$, define
$c_{I,\mathbf{a}}$ as in Equation 23.

Now, define $N:=\binom{n}{d}$ and for each tuple
$\overline{\mathbf{a}}=(\mathbf{a}^{(1)},\ldots,\mathbf{a}^{(N)})\in(\\{0,1\\}^{n-d})^{N}$,
compute the polynomial

$P_{\overline{\mathbf{a}}}(\mathbf{x})=\sum_{j=1}^{N}c_{I_{j},\mathbf{a}^{(j)}}\prod_{i\in
I_{j}}x_{i}$

where $I_{1},\ldots,I_{N}$ is some ordering of all subsets of $[n]$ of size
$d$.

Let $\mathcal{L}_{d}$ denote the set of all such polynomials.

##### Correctness.

Since $\delta(f,P)<1/2^{d}$, it follows that for each $I$ such that $|I|=d$,
there is at least one $\mathbf{a}\in\\{0,1\\}^{n-d}$ such that $f$ agrees with
$P$ on all inputs in the subcube $C_{\mathbf{a}}$ (as defined above). This
implies that there is at least one choice for the tuple
$\overline{\mathbf{a}}$ such that $P_{\overline{\mathbf{a}}}$ is exactly the
homogeneous component of $P$ of degree $d$.

##### Coefficients of smaller degree.

For each polynomial $P_{\overline{\mathbf{a}}}\in\mathcal{L}_{d}$, we define
$f_{\overline{\mathbf{a}}}$ by

$f_{\overline{\mathbf{a}}}(\mathbf{x})=f(\mathbf{x})-P_{\overline{\mathbf{a}}}(\mathbf{x})$

We now use the algorithm from Theorem A.1 on $f_{\overline{\mathbf{a}}}$ to
find the unique polynomial $Q_{\overline{\mathbf{a}}}$ of degree at most $d-1$
that is at distance less than $1/2^{d}$ from $f_{\overline{\mathbf{a}}}$.
Finally, we output the list of polynomials $\mathcal{L}$ where

$\mathcal{L}=\\{P_{\overline{\mathbf{a}}}+Q_{\overline{\mathbf{a}}}\ |\
\overline{\mathbf{a}}\\}.$

##### Correctness.

Define $P^{\prime}$ of degree $d-1$ as in the previous section. For any
$\overline{\mathbf{a}}$ such that $P_{\overline{\mathbf{a}}}$ is equal to the
homogeneous component of degree $d$ in $P,$ we see that
$\delta(f_{\overline{\mathbf{a}}},P^{\prime})=\delta(f,P)<1/2^{d}.$ By Theorem
A.1, we see that the polynomial $Q_{\overline{\mathbf{a}}}$ is equal to
$P^{\prime}.$ This implies that the list $\mathcal{L}$ contains the polynomial
$P.$ Since $P$ was an arbitrary degree $d$ polynomial such that
$\delta(f,P)<1/2^{d},$ the list $\mathcal{L}$ contains all such polynomials.

##### Running time.

Note that the number of $\overline{\mathbf{a}}$ is at most $(2^{n})^{N}\leq
2^{n^{d+1}}$. As the above algorithm runs in time $2^{O(n)}$ for each choice
of $\overline{\mathbf{a}}$, the overall running time is $2^{O(n^{d+1})}.$

##  Appendix B Improved Local Correction over Reals

In this section, we improve Theorem 3.1 by presenting an upper bound of
$q=\mathcal{O}(\log n/\log\log n)$ on the number of queries to correct degree
1 polynomials from $\\{0,1\\}^{n}$ to $\mathbb{R}$ when the relative error is
$\mathcal{O}(\log\log n/\log n)$.

######  Theorem B.1.

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

###### Proof.

The proof approach is similar to that of Theorem 3.1, except that we use a
different correction gadget in Lemma 3.4: we will show that we can find
$c_{1},\dots,c_{q}\in\mathbb{R}$ and a distribution $\mathcal{D}$ over
$(\\{0,1\\}^{n})^{q}$ such that

  * •

$c_{1}+\dots+c_{q}=1$ and for all $i\in[n]$ and any sample
$({\bf{y}}^{(1)},\dots,{\bf{y}}^{(q)})$ in the support of $\mathcal{D}$, we
have $c_{1}y^{(1)}_{i}+\dots+c_{q}y_{i}^{(q)}=1$.

  * •

For each $j\in[q]$, ${\bf{y}}^{(j)}$ is $\varepsilon$-close to $U_{n}$ for
some $\varepsilon=\sqrt{n}/q^{\Omega{(q)}}$ (Note that $\varepsilon$ was
$\sqrt{n}/2^{\Omega{(q)}}$ in Lemma 3.4).

Once we prove the existence of such $c_{j}$’s and $\mathcal{D}$, arguing along
the same lines as in Theorem 3.1 allows us to conclude that there is a
$(\delta,q)$-local correcting algorithm as long as
$\varepsilon=\sqrt{n}/q^{\Omega(q)}\leq 1/n$. Here we note that although the
argument in Theorem 3.1 was assuming $c_{j}$’s were integers, it still
continues to hold when they are arbitrary real numbers as we assume that the
underlying group is $\mathbb{R}$ in this section. Hence, we can take
$q=\mathcal{O}(\log n/\log\log n)$ with a sufficiently large constant factor.

Returning to proving the existence of $\mathcal{D}$ (and $c_{j}$’s), we define
the distribution $\mathcal{D}$ over $\\{0,1\\}^{n\times q}$ based on a
probability distribution $p$ over $[q]$ (we let $p_{j}:=\Pr[p=j]$ for
$j\in[q]$) and a matrix $M\in\\{0,1\\}^{q\times q}$ (we denote the $i$-th row
of $M$ by $M_{i}$, the $j$-th column by $M^{(j)}$ and the $(i,j)$-th entry by
$M_{ij}$) as follows:

  * •

For any $i\in[n]$, the $i$-th row of a sample from $\mathcal{D}$ is taken to
be $M_{j}$, where $j\sim p$ is chosen independently across different $i$.

With this definition of $\mathcal{D}$, we note that it suffices if
$M_{1}=(1,\dots,1)$ and $\left\langle M_{j},{\bf c}\right\rangle=1$ for all
$j\in[q]$ in order to satisfy Item 1, where ${\bf c}:=(c_{1},\dots,c_{q})$.
Item 2 shall be satisfied with a careful choice of $M$ and $p$. It will be
more convenient to work in $\\{\pm 1\\}$ notation instead of $\\{0,1\\}$: let
$N_{ij}:=1-2M_{ij}\in\\{\pm 1\\}$ for $i,j\in[q]$. Then the above conditions
can be equivalently written as $N_{1}=(-1,\dots,-1)$ and $\left\langle
N_{j},{\bf c}\right\rangle=\sum_{j}c_{j}-2\left\langle M_{j},{\bf
c}\right\rangle=-1$ for all $j\in[q]$. Note that a solution for ${\bf c}$
satisfying Item 1 always exists if $N$ is non-singular as it simply amounts to
solving $q$ linearly independent equations over $q$ variables.

To satisfy Item 2, we take $N$ to be an anti-Hadamard or ill-conditioned
matrix as constructed by Alon and Vu [AVu97] with some additional properties
(Items 3 and 4 below):

  1. 1.

$N$ is non-singular,

  2. 2.

the least singular value of $N$ is at most $1/q^{\Omega{(q)}}$, i.e., there
exists a non-zero vector $v\in\mathbb{R}^{q}$ such that
$\|N^{T}v\|_{2}/\|v\|_{2}\leq 1/q^{\Omega{(q)}}$,

  3. 3.

the vector $v$ above is a probability distribution, i.e., $v_{j}\geq 0$ for
all $j$ and $\sum_{j=1}^{q}v_{j}=1$, and

  4. 4.

the first row of $N$ is $N_{1}=(-1,\dots,-1)$.

Although the construction in [AVu97] does not directly guarantee Items 3 and
4, we can easily achieve them by flipping the sign of appropriate columns and
rows of $N$ and then by flipping and scaling the entries of $v$ (these changes
do not affect the least singular value). We now define the probability
distribution $p$ over $[q]$ to simply be $p_{j}=v_{j}$. This finishes the
description of the matrix $N$ and the distribution $\mathcal{D}$. It remains
to be shown for $({\bf y}^{(1)},\dots,{\bf y}^{(q)})\sim\mathcal{D}$ we have
that ${\bf y}^{(j)}$ is $\varepsilon$-close to $U_{n}$ for some
$\varepsilon=\sqrt{n}/q^{\Omega(q)}$. Since the entries of ${\bf y}^{(j)}$ are
mutually independent and the rows of $\mathcal{D}$ are sampled from the rows
of $M$, by 3.7 it suffices to show that for all $j\in[q]$, we have
$\left\lvert\operatorname*{\mathbb{E}}_{j^{\prime}\sim
p}[M_{j^{\prime}j}]-1/2\right\rvert\leq 1/q^{\Omega(q)}$. We prove this below:

$\displaystyle\left(\operatorname*{\mathbb{E}}_{j^{\prime}\sim
p}[M_{j^{\prime}j}]-1/2\right)^{2}$
$\displaystyle={\operatorname*{\mathbb{E}}_{j^{\prime}\sim
p}[N_{j^{\prime}j}]}^{2}/4$ (by definition of $N$)
$\displaystyle=\left(\sum_{j^{\prime}=1}^{q}p_{j^{\prime}}N_{j^{\prime}j}\right)^{2}/4={\left\langle
N^{(j)},v\right\rangle}^{2}/4$ (as $p_{j^{\prime}}=v_{j^{\prime}}$ by
definition) $\displaystyle\leq\sum_{j^{\prime\prime}=1}^{q}\left\langle
N^{(j^{\prime\prime})},v\right\rangle^{2}/4=v^{\top}NN^{\top}v/4=\|N^{\top}v\|_{2}^{2}/4$
$\displaystyle\leq\|v\|_{2}^{2}/q^{\Omega{(q)}}\leq 1/q^{\Omega{(q)}}.$ (using
Item 2 and $\|v\|_{2}^{2}\leq q$)

∎