# Perfect Zero-Knowledge PCPs for $\\#\mathsf{P}$

Tom Gur University of Cambridge. Email<EMAIL_ADDRESS>Jack O’Connor
University of Cambridge. Email<EMAIL_ADDRESS>Nicholas Spooner University
of Warwick/NYU. Email<EMAIL_ADDRESS>
###### Abstract

We construct perfect zero-knowledge probabilistically checkable proofs (PZK-
PCPs) for every language in $\\#\mathsf{P}$. This is the first construction of
a PZK-PCP for any language outside $\mathsf{BPP}$. Furthermore, unlike
previous constructions of (statistical) zero-knowledge PCPs, our construction
simultaneously achieves non-adaptivity and zero knowledge against arbitrary
(adaptive) polynomial-time malicious verifiers.

Our construction consists of a novel masked sumcheck PCP, which uses the
combinatorial nullstellensatz to obtain antisymmetric structure within the
hypercube and randomness outside of it. To prove zero knowledge, we introduce
the notion of locally simulatable encodings: randomised encodings in which
every local view of the encoding can be efficiently sampled given a local view
of the message. We show that the code arising from the sumcheck protocol (the
Reed–Muller code augmented with subcube sums) admits a locally simulatable
encoding. This reduces the algebraic problem of simulating our masked sumcheck
to a combinatorial property of antisymmetric functions.

###### Contents

  1. 1 Introduction
    1. 1.1 Our results
    2. 1.2 Acknowledgements
  2. 2 Techniques
    1. 2.1 Structure versus randomness
    2. 2.2 Combinatorial structure of antisymmetric functions
    3. 2.3 Local simulation of random low-degree extensions
    4. 2.4 Local simulation of subcube sums of LDEs
  3. 3 Preliminaries
    1. 3.1 Coding theory
    2. 3.2 Linear-algebraic claims
    3. 3.3 The combinatorial nullstellensatz
  4. 4 Locally simulatable encodings
    1. 4.1 Linear randomised encoding functions
  5. 5 Constraint location for random low-degree extensions
    1. 5.1 A constraint detector for random low-degree extensions of the zero function
    2. 5.2 The decision problem
    3. 5.3 Search-to-decision reduction
  6. 6 Constraint location for subcube sums of random low-degree extensions
    1. 6.1 Local characterisation of $\Sigma$RM
    2. 6.2 An $\ell$-constraint locator for $\Sigma$RM
  7. 7 Constraint location for $\Sigma$AntiSym
    1. 7.1 Properties of $\Sigma\mathrm{AntiSym}$
    2. 7.2 Algorithms for $\Sigma\mathrm{AntiSym}$
    3. 7.3 Proof of Theorem 7.2
  8. 8 ZKPCP for $\\#\mathsf{P}$
    1. 8.1 Zero-Knowledge Probabilistically Checkable Proofs (ZK-PCPs)
    2. 8.2 Our Construction
  9. A Deferred proofs
    1. A.1 Proof of 5.10
    2. A.2 Proof of Lemma 5.11
    3. A.3 Proof of 5.15
    4. A.4 Proof of Lemma 5.17
    5. A.5 Proof of 6.11

##  1 Introduction

The notion of a _zero-knowledge (ZK) proof_ , a proof that conveys no
information except the truth of a statement, is one of the most influential
ideas in cryptography and complexity theory of the past four decades.

Zero knowledge was originally defined by Goldwasser, Micali and Rackoff
[GMR89] in the context of interactive proofs (IPs). The deep and beautiful
insight in this work is that it is possible to rigorously _prove_ that an
interaction does not convey information, by exhibiting an efficient algorithm
called the _simulator_ which can generate the distribution of protocol
transcripts without interacting with the prover. In that work, the authors
identify three different notions of zero knowledge, depending on the quality
of the simulation. These are:  (1) _perfect_ zero knowledge (PZK), where the
simulator’s distribution is _identical_ to the real distribution of
transcripts;  (2) _statistical_ zero knowledge (SZK), where the distributions
are inverse-exponentially close; and  (3) _computational_ zero knowledge
(CZK), where the distributions are computationally indistinguishable.

This hierarchy led naturally to the study of the complexity classes
$\mathsf{PZK},\mathsf{SZK},\mathsf{CZK}$ of languages admitting ZK interactive
proofs. Seminal results show that $\mathsf{PZK}$ contains interesting “hard”
languages, including quadratic residuosity and nonresiduosity [GMR89] and
graph isomorphism and nonisomorphism [GMW91]. Despite this, the structure of
the class $\mathsf{PZK}$, and its relation to other complexity classes,
remains poorly understood. In light of this difficulty, the study of zero
knowledge has followed two main routes:  (1) studying the “relaxed” notions of
$\mathsf{SZK}$ and $\mathsf{CZK}$, and  (2) studying zero knowledge in other
models.

The former line of work has proved highly fruitful. A seminal result of
[GMW91] showed that $\mathsf{CZK}=\mathsf{IP}=\mathsf{PSPACE}$, which launched
the cryptographic study of ZK proofs, yielding a plethora of theoretical and
practical results [Tha22]. The study of $\mathsf{SZK}$ has revealed that this
class has a rich structure, and deep connections within complexity theory (cf.
[Vad99]).

The present work lies along the second route, also hugely influential. The
seminal work of Ben-Or, Goldwasser, Kilian, and Wigderson [BGKW88] introduced
the model of multi-prover interactive proofs (MIP) in order to achieve perfect
zero-knowledge without any computational assumptions [LS95, DFKNS92]. This in
turn inspired some of the most important models and results in contemporary
theoretical computer science, including entangled-prover interactive proofs
(MIP*), interactive oracle proofs (IOPs), and most notably, probabilistically
checkable proofs (PCPs). Indeed, the celebrated PCP theorem [ALMSS92, AS03,
Din07] is widely recognised as one of the most important achievements of
modern complexity theory [AAV13].

Zero-knowledge PCPs. Recall that a PCP is a proof which can be verified, with
high probability, by a verifier that only makes a small number of queries
(even $O(1)$) to the proof (cf. [AB09]). A zero-knowledge PCP is a
_randomised_ proof which, in addition to being locally checkable, satisfies a
zero knowledge condition: the view of any efficient (malicious) verifier can
be efficiently simulated (see [Wei22] for a survey). Similarly to the IP case,
we can distinguish PCPs with perfect, statistical and computational zero
knowledge. Note that there appears to be no formal relationship between ZK-IPs
and ZK-PCPs: standard transformations from IP to PCP spoil zero knowledge.

The first _statistical_ zero-knowledge PCPs appeared in the seminal work of
Kilian, Petrank and Tardos [KPT97]. Later works [IMS12, IW14] simplified this
construction, and extended it to PCPs of proximity. These constructions
operate via a 2-step compilation of (non-zero-knowledge) PCP: first the PCP is
endowed with honest-verifier statistical zero-knowledge (HVSZK), and then the
latter property is boosted into full statistical zero knowledge by “forcing”
the malicious verifier’s query pattern to be similarly distributed to that of
the honest verifier, using an object called a locking scheme. Kilian, Petrank
and Tardos use this transformation to prove that $\mathsf{NEXP}$ has SZK-PCPs
(with a polynomial-time verifier) that are zero knowledge against all
polynomial-time malicious verifiers; i.e.,
$\mathsf{SZK}\text{-}\mathsf{PCP}[\mathrm{poly},\mathrm{poly}]=\mathsf{NEXP}$.

Unfortunately, locking schemes have two inherent drawbacks: they require the
honest PCP verifier to be adaptive and they cannot achieve perfect zero
knowledge. Another line of work, motivated by cryptographic applications,
focuses on obtaining SZK-PCPs for NP with a _non-adaptive_ honest verifier
from leakage resilience. These results come with caveats, achieving either a
weaker notion of zero knowledge known as _witness indistinguishability_
[IWY16], or simulation against adversaries making only quadratically many more
queries than the honest verifier [HVW22].

The complexity landscape of perfect zero knowledge is subtle. As discussed
above, we know that $\mathsf{PZK\text{-}MIP}=\mathsf{MIP}=\mathsf{NEXP}$
[BGKW88], where $\mathsf{MIP}$ is the class of languages with a multi-prover
interactive proof. The quantum analogue of this result,
$\mathsf{PZK\text{-}MIP}^{*}=\mathsf{MIP}^{*}=\mathsf{RE}$, is also known to
hold [CFGS22, GSY19]. We know a similar result for interactive PCPs (IPCPs)
[KR08], an interactive generalisation of PCPs (and special case of IOPs):
$\mathsf{PZK\text{-}IPCP}=\mathsf{IPCP}=\mathsf{NEXP}$ [CFS17]. For IPs, the
picture is very different. We know that
$\mathsf{PZK}\subseteq\mathsf{SZK}\subseteq\mathsf{AM}\cap\mathsf{coAM}$
[For87, AH91], and so it is unlikely that $\mathsf{PZK}=\mathsf{IP}$
($=\mathsf{PSPACE}$), or even $\mathsf{NP}\subseteq\mathsf{PZK}$. It is
unknown whether $\mathsf{PZK}=\mathsf{SZK}$; indeed, it was recently shown
that there is an oracle relative to which this equality does not hold
[BCHTV20].

In contrast, _nothing at all_ is known about the class
$\mathsf{PZK}\text{-}\mathsf{PCP}$ except for the trivial inclusion
$\mathsf{BPP}\subseteq\mathsf{PZK}\text{-}\mathsf{PCP}$. In particular, the
following key question in the study of perfect zero knowledge remains open:

_Do perfect zero-knowledge PCPs exist for any non-trivial language?_

###  1.1 Our results

In this work, we give strong positive answer to this question, showing that
there exist perfect zero-knowledge PCPs (PZK-PCPs) for all of $\\#\mathsf{P}$.

######  Theorem 1 (Informally stated, see Theorem 8.1).

$\\#\mathsf{P}\subseteq\mathsf{PZK}\text{-}\mathsf{PCP}[\mathrm{poly},\mathrm{poly}]$.

We prove 1 by constructing a PZK-PCP for the $\\#\mathsf{P}$-complete language

$\\#\mathsf{SAT}=\\{(\Phi,N):\text{$\Phi$ is a CNF,
}\sum_{x\in\\{0,1\\}^{n}}\Phi(x)=N\\}.$

This is the first construction of a PZK-PCP for a language (believed to be)
outside $\mathsf{BPP}$. Furthermore, unlike previous constructions of zero-
knowledge PCPs, our construction simultaneously achieves _non-adaptivity_ for
the honest verifier and zero knowledge against arbitrary (adaptive)
polynomial-time malicious verifiers. We stress that 1 is unconditional and
does not rely on any cryptographic assumptions.

######  Remark 1.1.

As with its IP counterpart $\mathsf{PZK}$, $\mathsf{PZK}\text{-}\mathsf{PCP}$
is a class of _decision_ problems, and so the inclusion
$\\#\mathsf{P}\subseteq\mathsf{PZK}\text{-}\mathsf{PCP}$ refers to the
decision version of $\\#\mathsf{P}$ (for which $\\#\mathsf{SAT}$ is complete).
This class contains $\mathsf{UP}$ and $\mathsf{coNP}$ (in a natural way) but
may not contain $\mathsf{NP}$. Toda’s theorem, that
$\mathsf{PH}\subseteq\mathsf{P}^{\\#\mathsf{P}}$, does not directly imply that
$\mathsf{PH}\subseteq\mathsf{PZK}\text{-}\mathsf{PCP}$, as the $\\#\mathsf{P}$
oracle in this inclusion is a function oracle.

On the way to proving 1, we solve the following general algebraic-algorithmic
problem, which we consider to be of independent interest.

######  Problem 1 (Local simulation of low-degree extensions).

Given oracle access to a function $f\colon\\{0,1\\}^{m}\to\mathbb{F}$, where
$\mathbb{F}$ is a finite field, efficiently simulate oracle access to a
uniformly random _degree- $d$ extension_ of $f$; that is, a function
$\tilde{f}$ drawn uniformly at random from the set of $m$-variate polynomials
over $\mathbb{F}$ of individual degree $d$ that agree with $f$ on
$\\{0,1\\}^{m}$.

By “efficient” we mean polynomial in $m$, $d$ and $\log|\mathbb{F}|$. Chen et
al. [CCGOS23] give a _query-efficient_ simulator for $d\geq 2$, based on
observations of Aaronson and Wigderson [AW09]. (For $d=1$, there is a query
lower bound of $2^{m}$ [JKRS09].) In this work we give a _computationally_
efficient simulator for $d\geq 2$.

######  Theorem 2 (informal, see Theorem 5.4).

There is an efficient algorithm solving 1 for $d\geq 2$.

###  1.2 Acknowledgements

The authors thank Alessandro Chiesa, Hendrik Waldner and Arantxa Zapico for
helpful discussions. TG is supported by UKRI Future Leaders Fellowship
MR/S031545/1, EPSRC New Horizons Grant EP/X018180/1, and EPSRC RoaRQ Grant
EP/W032635/1.

##  2 Techniques

We start by outlining how to construct (non-ZK) PCPs for $\\#\mathsf{SAT}$ via
the sumcheck protocol [LFKN92]. Recall that the prover and verifier in the
sumcheck protocol have oracle access to an $m$-variate polynomial $P$ (the
arithmetisation of $\Phi$) of individual degree $d$ over a finite field
$\mathbb{F}$, and the prover wishes to convince the verifier that
$\sum_{\vec{a}\in\\{0,1\\}^{m}}P(\vec{a})=\gamma$ for some
$\gamma\in\mathbb{F}$. This is achieved via a $2m$-message protocol, in which
for every $i\in[m]$,

  * •

the $2i$-th message, sent by the verifier, is a uniformly random challenge
$c_{i}\in\mathbb{F}$; and

  * •

the $(2i-1)$-th message, sent by the prover, is the univariate polynomial

$g_{i}(X)=\sum_{\vec{a}\in\\{0,1\\}^{m-i}}P(c_{1},\ldots,c_{i-1},X,a_{i+1},\ldots,a_{m}).$

The verifier accepts if  (a) $g_{1}(0)+g_{1}(1)=\gamma$;  (b) for each $1\leq
i\leq m-1$, $g_{i}(c_{i})=g_{i+1}(0)+g_{i+1}(1)$; and  (c)
$g_{m}(c_{m})=P(c_{1},\ldots,c_{m})$.  This protocol is complete and sound for
sufficiently large $\mathbb{F}$. Moreover, we can “unroll” the interactive
sumcheck protocol into an (exponentially large) PCP by writing down the
prover’s answers to each possible (sub-)sequence of challenges.

Unfortunately, the sumcheck PCP is _clearly not zero knowledge_ : even the
prover’s first message $g_{1}$ reveals information about $P$ which is
$\\#\mathsf{P}$-hard to compute. In this overview, we will explain how to
modify the sumcheck PCP in order to achieve perfect zero knowledge.

#### Zero knowledge IOPs.

Our approach to constructing a PZK-PCP for sumcheck is inspired by the
[BCFGRS17] construction of a perfect zero knowledge sumcheck in the
_interactive oracle proof_ (IOP) model. The IOP model is an interactive
generalisation of PCPs, in which the prover and verifier interact across
multiple rounds, with the prover sending a PCP oracle in each round.

In their IOP, the prover first sends the evaluation table of a uniformly
random $m$-variate polynomial $R$ such that
$\sum_{\vec{a}\in\\{0,1\\}^{m}}R(\vec{a})=0$, which will be used as a mask.
Next, to ensure soundness in case $R$ does not sum to zero, the verifier sends
a challenge $\alpha$. Finally, the prover sends a sumcheck PCP for the
statement $\sum_{\vec{a}\in\\{0,1\\}^{m}}\alpha
P(\vec{a})+R(\vec{a})=\alpha\gamma$.

Intuitively, this protocol does not leak much information about $P$, because
$\alpha P+R$ is a _uniformly random_ polynomial that sums to $\alpha\gamma$.
[BCFGRS17] shows, using techniques from algebraic complexity theory, that this
IOP is indeed perfect zero knowledge; we will make use of these techniques
later in our construction.

Unfortunately, the interaction in this protocol is crucial in order to balance
soundness and zero knowledge. Indeed, one could imagine “unrolling” this IOP
into a PCP in the same way as for sumcheck itself: writing down, for each
$\alpha\in\mathbb{F}$, a sumcheck PCP $\Pi_{\alpha}$ for $\alpha P+R$. This
preserves soundness, but completely breaks zero knowledge: since the sumcheck
PCP is a linear function of the underlying polynomial, given any _two_
$\Pi_{\alpha},\Pi_{\alpha^{\prime}}$ for distinct $\alpha,\alpha^{\prime}$, we
can recover the sumcheck PCP for $P$ as
$(\Pi_{\alpha}-\Pi_{\alpha^{\prime}})/(\alpha-\alpha^{\prime})$.

On the other hand, if we have the prover send only _one_ $\Pi_{\alpha}$, then
soundness is lost, as the prover can easily cheat by sending $R$ that does not
sum to zero. We could attempt to fix the soundness issue by having the prover
additionally _prove_ , via another sumcheck PCP $\Pi_{R}$, that
$\sum_{\vec{a}}R(\vec{a})=0$. While this would restore soundness, we once
again lose zero knowledge, as the sumcheck PCP for $P$ can be recovered as
$(\Pi_{\alpha}-\Pi_{R})/\alpha$.

###  2.1 Structure versus randomness

From the above discussion, we see that the central obstacle to obtaining a
zero knowledge PCP is that the prover can break soundness by sending some $R$
with $\sum_{\vec{a}}R(\vec{a})\neq 0$, and known methods for detecting this
strategy (without interaction) break zero knowledge.

Our approach is to _prevent_ this malicious prover strategy by choosing a
polynomial $R$ so that $\sum_{\vec{a}}R(\vec{a})=0$ _by definition_. Of
course, we must take care to ensure that $R$ still hides certain information
about $P$. But what kind of information? We observe that, without loss of
generality, we can view the sumcheck PCP for $P+R$ as an oracle $\Pi$ such
that

$\Pi(c_{1},\ldots,c_{i})=\sum_{\vec{a}\in\\{0,1\\}^{m-i}}(P+R)(c_{1},\ldots,c_{i},a_{i+1},\ldots,a_{m})~{},$

for all $i\in[m]$ and $c_{1},\ldots,c_{i}\in\mathbb{F}$. Computing the
“subcube sum”
$\sum_{\vec{a}\in\\{0,1\\}^{m-i}}P(c_{1},\ldots,c_{i},a_{i+1},\ldots,a_{m})$
requires $2^{m-i}$ queries to $P$. Hence, in order to hope to simulate, we
must ensure that $R$ hides such subcube sums for any $1\leq i<m-O(\log m)$.
So, at a minimum, it should be the case that for all such $i$, and all
$c_{1},\ldots,c_{i}\in\mathbb{F}$, the subcube sum
$\sum_{\vec{a}\in\\{0,1\\}^{m-i}}R(c_{1},\ldots,c_{i},a_{i+1},\ldots,a_{m})$
is marginally uniform.

In short: (1) for soundness, we need that the _full_ sum of the masking
polynomial $R$ over the hypercube $\\{0,1\\}^{n}$ is fixed, and (2) for zero
knowledge, other than sum over the hypercube, we would like $R$ to be
distributed as random as possible.

We start by ensuring that any _partial_ subcube sum of $R$ is distributed
uniformly at random. Our key observation here is that while the full sum is
_invariant_ under any reordering of the variables $X_{1},\ldots,X_{m}$, any
nontrivial subcube sum ($i<m$) is _not_. This leads us to the following choice
for the masking polynomial:

$R(X_{1},\ldots,X_{m})\ {:=}\
Q(X_{1},X_{2},\ldots,X_{m})-Q(X_{m},X_{m-1},\ldots,X_{1})~{},$

where $Q$ is a uniformly random $m$-variate polynomial of individual degree
$d$.

Clearly, by the permutation invariance of the complete sum,
$\sum_{\vec{a}\in\\{0,1\\}^{m}}R(\vec{a})=0$. On the other hand, consider the
special case of a subcube sum of $R$ on the hypercube, i.e., for
$(c_{1},\ldots,c_{i})\in\\{0,1\\}^{i}$:

$\sum_{\vec{a}\in\\{0,1\\}^{m-i}}Q(c_{1},\ldots,c_{i},a_{i+1},\ldots,a_{m})-\sum_{\vec{a}\in\\{0,1\\}^{m-i}}Q(a_{m},\ldots,a_{i+1},c_{i},\ldots,c_{1})~{}.$

This expression can only be identically zero for all $Q$ if
$\\{c_{1}\\}\times\cdots\times\\{c_{i}\\}\times\\{0,1\\}^{m-i}=\\{0,1\\}^{m-i}\times\\{c_{i}\\}\times\cdots\times\\{c_{1}\\}$,
which is clearly only possible if $i\in\\{0,m\\}$. By linearity, if this
subcube sum is not identically zero for all $Q$, then it is uniform when $Q$
is uniform.

Still, compared to the IOP case, the masking polynomial $R$ has extra
structure: it satisfies an “antisymmetry”
$R(\alpha_{1},\ldots,\alpha_{m})=-R(\alpha_{m},\ldots,\alpha_{1})$ for all
$(\alpha_{1},\ldots,\alpha_{m})\in\mathbb{F}^{m}$. This structure means that
$P+R$ is no longer uniformly random and may leak nontrivial information about
$P$.

To mitigate this, we modify $R$ to make it “as random as possible” while
preserving antisymmetry on $\\{0,1\\}^{m}$ and low-degree structure over
$\mathbb{F}^{m}$. Our final choice of $R$ is as follows:

$R(\vec{X})=Q(\vec{X})-Q(\vec{X}_{\mathsf{rev}})+\sum_{i=1}^{m}X_{i}(1-X_{i})T_{i}(\vec{X})~{},$
(1)

where $Q$ is as before, $\vec{X}_{\mathsf{rev}}\ {:=}\ (X_{m},\ldots,X_{1})$,
and each $T_{i}$ is a uniformly random $m$-variate polynomial where
$\deg_{X_{i}}(T_{i})=d-2$ and $\deg_{X_{j}}(T_{i})=d$ for $j\neq i$. What is
this extra term? It was observed by [CCGOS23], via the combinatorial
nullstellensatz [Alo99], that $Z(\vec{X})\ {:=}\
\sum_{i=1}^{m}X_{i}(1-X_{i})T_{i}(\vec{X})$ is a uniformly random polynomial
subject to the condition that, for all $\vec{a}\in\\{0,1\\}^{m}$,
$Z(\vec{a})=0$. Adding this to $R$ retains the antisymmetric structure on the
hypercube, but has the effect of “masking out” any structure that appears
outside of $\\{0,1\\}^{m}$; in particular, $R$ is no longer antisymmetric over
all of $\mathbb{F}^{m}$.

#### Key challenge: local simulation of combinatorial and algebraic structure.

Showing the completeness and soundness of the PCP obtained via the foregoing
approach is straightforward. Hence, it remains to prove that the perfect zero-
knowledge condition holds.

Starting with the trivial case, note that our observation about subcube sums
in the discussion above provides a simple strategy for simulating any _single_
query $(c_{1},\ldots,c_{i})$ _within the hypercube_ $\\{0,1\\}^{i}$ to $\Pi$.
Alas, this clearly does not suffice, as even the honest sumcheck verifier
makes multiple queries to the proof, for
$(c_{1},\ldots,c_{i})\notin\\{0,1\\}^{i}$, Hence, we must simulate multiple
queries beyond the hypercube.

Indeed, the simulation of multiple queries to the low-degree extension of the
hypercube is where the key challenge arises. More specifically, the difficulty
is that our masking polynomial $R$ has both _algebraic_ structure arising from
the polynomial degree bound and _combinatorial_ structure arising from the
antisymmeric reordering of the variables. In order to simulate, we must not
only understand both types of structure, but crucially, also _how they
interact_.

In the remainder of this proof overview, we explain how we design an efficient
simulator that can simulate responses to any number of queries to $\Pi$ (the
sumcheck PCP for $P+R$), over the entire space $\mathbb{F}^{\leq m}$. Towards
this end, we introduce the notion of _locally-simulatable encodings_.

Loosely speaking, locally-simulatable encodings are randomised encodings in
which every local view of the encoding can be efficiently sampled from a local
view of the message. More precisely, we say that a randomised encoding
function $\mathsf{ENC}\colon(H\to\mathbb{F})\to(D\to\mathbb{F})$ is locally
simulatable if there is an algorithm $\mathcal{S}$ which, given oracle access
to a message $m\colon H\to\mathbb{F}$ and a set $S\subseteq D$, samples from
the distribution of $\mathsf{ENC}(m)|_{S}\subseteq\mathbb{F}^{S}$ in time
polynomial in $|S|$ (which may be much less than $|H|$).

The notion of locally-simulatable encodings is tightly connected to ZKPCPs: we
can view the mapping from instances to corresponding PCPs as a randomised
encoding. A local simulator for this encoding is a zero knowledge simulator
for the PCP system.111To handle malicious verifiers that make adaptive
queries, we will actually require a stronger notion of local simulation that
allows for conditional sampling; see Section 4 for details. In the following
sections, we will provide an overview of the proofs that the combinatorial
antisymmetric structure of our masking, the algebraic structure of the Reed-
Muller code, and their augmentations with subcube sums that arise in the
sumcheck protocol admit locally simulatable encodings.

###  2.2 Combinatorial structure of antisymmetric functions

As discussed above, the response to any _single_
$(c_{1},\ldots,c_{i})\in\\{0,1\\}^{i}$ to $\Pi$ can be perfectly simulated. In
this section, we explain how to simulate any number of queries to $\Pi$,
provided that those queries lie in the set $\\{0,1\\}^{\leq m}\ {:=}\
\cup_{i=1}^{m}\\{0,1\\}^{i}$. Note that evaluated over the hypercube, the last
term of Eq. 1 cancels, hence we can think of the masking polynomials as
$R(\vec{X})=Q(\vec{X})-Q(\vec{X}_{\mathsf{rev}})$, where
$\vec{X}_{\mathsf{rev}}\ {:=}\ (X_{m},\ldots,X_{1})$.

Observe that, when restricted to $\\{0,1\\}^{m}$, the distribution of $R$ is
well structured; namely, it is a uniformly random element of the vector space
$\mathrm{AntiSym}$ of “antisymmetric functions”222This is terminology that we
introduce, which is distinct from the usual notion of antisymmetry for
polynomials., i.e., functions $f\colon\\{0,1\\}^{m}\to\mathbb{F}$ such that
for all $\vec{c}\in\\{0,1\\}^{m}$, $f(\vec{c})=-f(\vec{c}_{\mathsf{rev}})$,
where $\vec{c}_{\mathsf{rev}}=(c_{m},\ldots,c_{1})$ is the reverse of
$\vec{c}$. We can view the restriction of $\Pi$ to $\\{0,1\\}^{\leq m}$ as the
output of a randomised encoding function
$\mathsf{ENC}_{\Sigma\mathrm{AntiSym}}\colon(\\{0,1\\}^{m}\to\mathbb{F})\to(\\{0,1\\}^{m}\to\mathbb{F})$,
applied to the restriction of $P$ to $\\{0,1\\}^{m}$. The function
$\mathsf{ENC}_{\Sigma\mathrm{AntiSym}}$ has the following description.

  * $\mathsf{ENC}_{\Sigma\mathrm{AntiSym}}(f)$:

    1. 1.

Choose a uniformly random $r\in\mathrm{AntiSym}$.

    2. 2.

Output the function $\Sigma[f+r]$, given by

$\Sigma[f+r](c_{1},\ldots,c_{i})\ {:=}\
\sum_{\vec{a}\in\\{0,1\\}^{m-i}}(f+r)(c_{1},\ldots,c_{i},a_{i+1},\ldots,a_{m})~{},$
(2)

for all $i\in[m]$; i.e., the function $f+r$, augmented with all of its subcube
sums.

In this perspective, our task is now to provide a local simulator for
$\mathsf{ENC}_{\Sigma\mathrm{AntiSym}}$. That is, for a query set
$S\subseteq\\{0,1\\}^{\leq m}$, we want to efficiently simulate
$\Sigma[f+r]|_{S}$ for a uniformly random $r\in\Sigma\mathrm{AntiSym}$, given
oracle access to $f$.

Let $\Sigma\mathrm{AntiSym}|_{S}$ denote the vector space
$\\{\Sigma[r]|_{S}:r\in\mathrm{AntiSym}\\}$, and let $B$ be a basis for its
dual code $(\Sigma\mathrm{AntiSym}|_{S})^{\perp}$; that is,
$v\in\Sigma\mathrm{AntiSym}|_{S}$ if and only if $Bv=0$. Then, by linearity,
$\Sigma[f+r]|_{S}$ is distributed as a uniformly random vector $w\colon
S\to\mathbb{F}$ such that $Bw=B(\Sigma[f]|_{S})$.

With this in mind, our local simulator $\mathcal{S}$ could work as follows.

  * $\mathcal{S}^{f}(S)$:

    1. 1.

Compute a basis $B$ for $(\Sigma\mathrm{AntiSym}|_{S})^{\perp}$.

    2. 2.

Compute $y=B(\Sigma[f]|_{S})$ by querying $f$ as necessary.

    3. 3.

Output a random $w$ such that $Bw=y$.

Correctness is straightforward. The only potential issue is efficiency:
evaluating $\Sigma[f]$ at a point in $S$ may require exponentially many
queries to $f$. Note, however, that if the column of $B$ corresponding to
$\vec{c}\ {:=}\ (c_{1},\ldots,c_{i})$ is all zero, then we do not need to know
$\Sigma[f](c_{1},\ldots,c_{i})$ to compute $B(\Sigma[f]|_{S})$. Hence, for
efficiency, it would suffice to (efficiently) find a basis $B$ for
$(\Sigma\mathrm{AntiSym}|_{S})^{\perp}$ such that
$\sum_{\vec{c}\in\mathsf{supp}(B)}2^{m-\ell(\vec{c})}=\mathrm{poly}(|S|)$,
where $\mathsf{supp}(B)$ is the set of nonzero columns of $B$ and
$\ell(\vec{(})c)=i$ for $c\in\\{0,1\\}^{i}$.

Does such a basis exist? Not exactly: for example, if $S=\\{(0),(1)\\}$, then
$\mathsf{supp}(B)=\\{(0),(1)\\}$, since
$\Sigma[r](0)+\Sigma[r](1)=\sum_{\vec{a}\in\\{0,1\\}^{m-1}}r(0,\vec{a})+\sum_{\vec{a}\in\\{0,1\\}^{m-1}}r(1,\vec{a})=0$
for all $r\in\mathrm{AntiSym}$. However, this counterexample does not actually
cause a problem for zero knowledge, since for this basis $B$, it holds that
$B(\Sigma[P]|_{S})=\sum_{\vec{a}\in\\{0,1\\}^{m}}P(\vec{a})=\gamma$, which is
part of the input to the problem. Our key technical result in this section is
that all possible counterexamples are essentially of this form.

######  Lemma 1.

There is a polynomial $p$ such that, for any prefix-free333A set
$S\subseteq\\{0,1\\}^{\leq m}$ is _prefix-free_ if for any
$\vec{c}_{1},\vec{c}_{2}\in S$, if $\vec{c}_{1}$ is a prefix of $\vec{c}_{2}$
then $\vec{c}_{1}=\vec{c}_{2}$. $S\subseteq\\{0,1\\}^{\leq m}$, there exists a
basis $B$ of $(\Sigma\mathrm{AntiSym}|_{S})^{\perp}$ where each row $b_{i}$ of
$B$ is a $0$-$1$ vector, and letting $T(b_{i})\ {:=}\
\\{(\vec{c},\vec{a}):b_{i}(\vec{c})=1,\vec{a}\in\\{0,1\\}^{m-|\vec{c}|}\\}$,
either

$|T(b_{i})|\leq p(|S|)\qquad\text{ or }\qquad|T(b_{i})|\geq 2^{m}-p(|S|)~{}.$

Moreover, $B$ can be efficiently computed from $S$.

For the purposes of this overview, we will assume that $S$ is indeed prefix-
free; in the full proof we show that this holds without loss of generality.

To gain some intuition for this result, let us consider the 2-dimensional case
of antisymmetric functions $A\colon[n]^{2}\to\mathbb{F}$; i.e., $n\times n$
antisymmetric matrices $A$ over $\mathbb{F}$. Suppose that
$X\subseteq[n]\times[n]$ is a set consisting of $r$ full rows and $t$
individual entries (so $|X|=rn+t$) such that for all antisymmetric $A$, it
holds that $\sum_{(i,j)\in X}a_{ij}=0$. The latter condition implies that the
indicator matrix for $X$ must be symmetric; one possible choice of $X$ is
highlighted in Fig. 1. It is straightforward to show that this symmetry
implies $t\geq r\cdot(n-r)$, from which we obtain the pair of inequalities

$r\leq\frac{1}{2}\cdot
n\left(1-\sqrt{1-\frac{4t}{n^{2}}}\right)\approx\frac{t}{n}+\frac{t^{2}}{n^{3}}\quad\text{or}\quad
r\geq\frac{1}{2}\cdot n\left(1+\sqrt{1-\frac{4t}{n^{2}}}\right)\approx
n-\frac{t}{n}-\frac{t^{2}}{n^{3}}~{}.$

This in turn yields appropriate bounds on $|X|$: $|X|\lesssim 2t+t^{2}/n^{2}$
or $|X|\gtrsim n^{2}-t^{2}/n^{2}$. The proof of 1 generalises this approach to
higher dimensions.

$\left(\begin{array}[]{ccccc}0&\vphantom{\Big{|}}\text{\hbox{\pagecolor{yellow!40}$a_{12}$}}&\text{\hbox{\pagecolor{yellow!40}$a_{13}$}}&a_{14}&a_{15}\\\
-a_{12}&0&a_{23}&a_{24}&a_{25}\\\ -a_{13}&-a_{23}&0&a_{34}&a_{35}\\\
-a_{14}&\vphantom{\Big{|}}\text{\hbox{\pagecolor{yellow!40}$-a_{24}$}}&\text{\hbox{\pagecolor{yellow!40}$-a_{34}$}}&0&a_{45}\\\
-a_{15}&\text{\hbox{\pagecolor{yellow!40}$-a_{25}$}}&\text{\hbox{\pagecolor{yellow!40}$-a_{35}$}}&-a_{45}&\text{\hbox{\pagecolor{yellow!40}$0$}}\end{array}\right)$
Figure 1: A general antisymmetric matrix ($n=5$), with an element of the dual
highlighted ($r=2,t=7$).

1 suggests the following modified local simulator, which we additionally
provide with the total sum $\gamma$:

  * $\mathcal{S}_{\mathrm{AntiSym}}^{f}(S;\gamma)$:

    1. 1.

Compute a basis $B$ for $(\Sigma\mathrm{AntiSym}|_{S})^{\perp}$ as in 1.

    2. 2.

For each row $b_{i}$ of $B$:

      1. (a)

if $|T(b_{i})|\leq 2^{m-1}$, compute $y_{i}=\sum_{\vec{x}\in
T(b_{i})}f(\vec{x})$;

      2. (b)

otherwise, compute $y_{i}=\gamma-\sum_{\vec{x}\in\\{0,1\\}^{m}\setminus
T(b_{i})}f(\vec{x})$.

    3. 3.

Output a random $w$ such that $Bw=y$.

Clearly, the number of queries to $f$ required is
$\min(|T(b_{i})|,2^{m}-|T(b_{i})|)$, which is $\mathrm{poly}(|S|)$ by 1; hence
the overall running time of the simulator is $\mathrm{poly}(|S|)$.

###  2.3 Local simulation of random low-degree extensions

In the previous section we addressed the _combinatorial_ problem of simulating
queries to $\Pi$ that lie in the set $\\{0,1\\}^{\leq m}$, which exhibits
antisymmetric strucutre. In this section we consider the _algebraic_ problem
of simulating queries to $\Pi$ that also lie outside of the hypercube (i.e.,
general point queries), which exhibits pseudorandom structure. We then bring
these two parts together in Section 2.4.

Recall that our choice of $R$ is

$R(\vec{X})=Q(\vec{X})-Q(\vec{X}_{\mathsf{rev}})+\sum_{i=1}^{m}X_{i}(1-X_{i})T_{i}(\vec{X})~{},$

where $Q$ is as before, $\vec{X}_{\mathsf{rev}}\ {:=}\ (X_{m},\ldots,X_{1})$,
and each $T_{i}$ is a uniformly random $m$-variate polynomial where
$\deg_{X_{i}}(T_{i})=d-2$ and $\deg_{X_{j}}(T_{i})=d$ for $j\neq i$.

Denote by $\mathrm{RM}[\mathbb{F},m,d]\subseteq\mathbb{F}^{m}\to\mathbb{F}$
the _Reed–Muller_ code of evaluations of $m$-variate polynomials of individual
degree $d$ over $\mathbb{F}$. For a function
$f\colon\\{0,1\\}^{m}\to\mathbb{F}$, denote by $\mathsf{LD}[f,d]\ {:=}\
\\{\hat{f}\in\mathrm{RM}[\mathbb{F},m,d]:\hat{f}(x)=f(x)\,\forall\vec{x}\in\\{0,1\\}^{m}\\}$
the set of _degree- $d$ extensions_ of $f$. With the above modification, we
can describe the sumcheck PCP for $P+R$, restricted to $\mathbb{F}^{m}$, as
the output of the following randomised encoding:

  * $\mathsf{ENC}_{\mathrm{RM}\mathrm{AntiSym}}(P)$:

    1. 1.

Sample a random antisymmetric function $f\colon\\{0,1\\}^{m}\to\mathbb{F}$.

    2. 2.

Sample $R$ uniformly at random from $\mathsf{LD}[f,d]$.

    3. 3.

Output $P+R$.

Our problem now becomes to design a local simulator for
$\mathsf{ENC}_{\mathrm{RM}\mathrm{AntiSym}}$.

We will do this by solving a much more general problem: _we prove that random
low-degree extensions are locally simulatable._ More precisely, let
$\mathsf{ENC}_{\mathrm{RM}}^{d}(f)$ be the encoding function that outputs a
uniformly random element of $\mathsf{LD}[f,d]$. We prove that
$\mathsf{ENC}_{\mathrm{RM}}^{d}$ has a local simulator
$\mathcal{S}_{\mathrm{RM}}^{d}$ for any $d\geq 2$. We can then easily obtain a
simulator for $\mathsf{ENC}_{\mathrm{RM}\mathrm{AntiSym}}$ by composing
$\mathcal{S}_{\mathrm{RM}}$ with the local simulator for $\mathrm{AntiSym}$
described in the previous section.

Our starting point. We will build on the “stateful emulator” that was
constructed in [CCGOS23] (for a particular oracle model that they introduced),
which can be conceptualised as an _inefficient_ local simulator for
$\mathsf{ENC}_{\mathrm{RM}}$. To describe it, we first introduce some
notation.

For $w\in\\{0,1\\}^{m}$, we denote by $\delta_{w}$ the unique multilinear
polynomial satisfying $\delta_{w}(w)=1$ and $\delta_{w}(x)=0$ for all
$x\in\\{0,1\\}^{m}\setminus\\{w\\}$. For a set $S\subseteq\mathbb{F}^{m}$, we
say that $w$ is _$S$ -good_ if there exists an $m$-variate polynomial $q_{w}$
of individual degree at most $d$ such that  (i) $q_{w}(x)=0$for every
$x\in\\{0,1\\}^{m}\setminus\\{w\\}$;  (ii) $q_{w}(z)=0$for every $z\in S$; and
(iii) $q_{w}(w)=1$ . We say that $w$ is _$S$ -bad_ if it is not $S$-good.
Intuitively, when $\hat{f}$ is a uniformly random low-degree extension of $f$,
$\hat{f}|_{S}$ only conveys information about $f(w)$ for $S$-bad points $w$.
For example, any point in $\\{0,1\\}^{m}\cap S$ is trivially $S$-bad. Less
trivially, if $S$ consists of sufficiently many points on a curve passing
through $w\in\\{0,1\\}^{m}$, then $w$ may be $S$-bad even if
$\\{0,1\\}^{m}\cap S$ is empty.

The simulator of Chen et al. works roughly as follows:444Their analysis
requires sampling $P$ in a different (and more complicated) way.

  * $\mathcal{S}^{f}_{\mathrm{RM}}(S)$:

    1. 1.

Compute the set of $S$-bad points $W$.

    2. 2.

Query $f(w)$ at all $w\in W$, sample a uniformly random polynomial $P$ such
that $P(w)=f(w)$ for all $w\in W$, and output $P|_{S}$.

Chen et al. prove that $\mathcal{S}_{\mathrm{RM}}$ is correct, and moreover
that it is _query-efficient_ , provided that $d\geq 2$: the number of queries
it makes to $f$ (equal to $|W|$) is at most $|S|$ (this follows from [AW09,
Lemma 4.3]).

However, they leave open the question of whether $\mathcal{S}_{\mathrm{RM}}$
can be made _computationally_ efficient. We note that Step 2 can be achieved
efficiently using an algorithm of [BCFGRS17]. The issue is in Step 1; namely,
it is not clear how to compute the set $W$ from $S$. Indeed, at first glance
this appears to be hopeless: naively, computing whether a single $w$ is
$S$-bad requires solving an exponentially large linear system, and there are
$2^{m}$ possible choices for $w$. Nonetheless, we will present an efficient
algorithm which, given $S$, outputs a list of all $S$-bad points.555Chen et
al. follow a different route: roughly, they show that because their $f$ is
_extremely sparse_ , it is very unlikely that $f(w)\neq 0$ for any $w\in
W\setminus S$, and so for simulation one can pretend that $f$ is zero on
$\\{0,1\\}^{m}\setminus S$. This does not work for us for two reasons: first,
a random antisymmetric function is not sparse with overwhelming probability,
and second, this strategy introduces a small statistical error in simulation,
which would spoil perfect zero knowledge.

Step 1: solving the decision problem. Our first step is to consider the
_decision_ variant of this problem: given a set $S$, does there _exist_ an
$S$-bad $w$? Our key insight here is that we can relate the existence of an
$S$-bad $w$ to the dimension of the vector space $\mathsf{LD}[Z,d]|_{S}$,
where $Z$ is the constant zero function. We show that all $w$ are $S$-good if
and only if $\mathsf{LD}[Z,d]|_{S}=\mathrm{RM}[\mathbb{F},m,d]|_{S}$. Indeed,
if every $w$ is $S$-good, then for any degree-$d$ polynomial $P$, the
polynomial $P-\sum_{w\in\\{0,1\\}^{m}}P(w)\cdot q_{w}$ is a degree-$d$
extension of $Z$ that agrees with $P$ on $S$. On the other hand, if
$\mathsf{LD}[Z,d]|_{S}=\mathrm{RM}[\mathbb{F},m,d]|_{S}$, then for every $w$,
there is a $\hat{Z}_{w}\in\mathsf{LD}[Z,d]$ that agrees with $\delta_{w}$ on
$S$; hence we can take $q_{w}=\delta_{w}-\hat{Z}_{w}$, and so $w$ is $S$-good.

Hence to solve the decision problem it suffices to compute (the dimensions of)
$\mathrm{RM}[\mathbb{F},m,d]|_{S}$ and $\mathsf{LD}[Z,d]|_{S}$. The former can
be achieved efficiently (in time $\mathrm{poly}(|S|,m,d,\log|\mathbb{F}|)$)
using the _succinct constraint detector_ for Reed–Muller discovered by
[BCFGRS17].

To compute the latter, we build on ideas introduced in [CCGOS23]. As discussed
above, in that work the authors observe that to sample a vector
$v\leftarrow\mathsf{LD}[Z,d]|_{S}$, it suffices to (lazily) sample random
polynomials $T_{i}$, $i\in[m]$, of the appropriate degrees, and then set
$v(\vec{\alpha})\ {:=}\
\sum_{i=1}^{m}\alpha_{i}(1-\alpha_{i})T_{i}(\vec{\alpha})$ for each
$\vec{\alpha}\in S$. Similarly, we show how to compute a basis for
$\mathsf{LD}[Z,d]|_{S}$ by combining bases for the subspaces $\mathcal{P}_{i}\
{:=}\
\\{T_{i}|_{S}\in\mathrm{RM}[\mathbb{F},d,m]|_{S}:\deg_{X_{i}}(T_{i})=d-2\\}$,
for $i\in[m]$. These bases can also be computed using the succinct constraint
detector for Reed–Muller; see Section 5.

Step 2: search-to-decision reduction. Next, we will build upon the techniques
we developed in Step 1 to solve the original search problem. A natural
strategy is to employ a binary search: for each $b\in\\{0,1\\}$, test if
$\\{b\\}\times\\{0,1\\}^{m-1}$ contains any $S$-bad points, and recurse if it
does. Since the number of $S$-bad points is bounded by $|S|$, the recursion
will terminate quickly. It therefore suffices to give an efficient algorithm
that, given a set $A$ of the form
$\\{a_{1}\\}\times\cdots\times\\{a_{i}\\}\times\\{0,1\\}^{m-i}$, determines
whether $A$ contains any $S$-bad point.

For $A\subseteq\\{0,1\\}^{m}$, let $\mathsf{LD}[Z_{A},d]|_{S}\ {:=}\
\\{P\in\mathrm{RM}[\mathbb{F},m,d]:P(\vec{x})=0\,\forall\vec{x}\in A\\}$. Our
algorithm for computing a basis for $\mathsf{LD}[Z,d]|_{S}$ can be
straightforwardly extended to compute a basis for $\mathsf{LD}[Z_{A},d]|_{S}$.
We can also extend the reasoning from Step 1 to show that if every $w\in A$ is
$S$-good, then $\mathsf{LD}[Z_{A},d]|_{S}=\mathrm{RM}[\mathbb{F},m,d]|_{S}$.
Unfortunately, the converse does not hold: it may be that $A$ contains $S$-bad
points but $\mathsf{LD}[Z_{A},d]|_{S}=\mathrm{RM}[\mathbb{F},m,d]|_{S}$. This
can happen, for example, if $S$ contains points on a curve passing through
both $w\in A$ and $w^{\prime}\in\\{0,1\\}^{m}\setminus A$. In particular, the
argument from Step 1 fails: for $\hat{Z}_{w}\in\mathsf{LD}[Z_{A},d]$,
$\delta_{w}-\hat{Z}_{w}$ is not necessarily zero on $\\{0,1\\}^{m}\setminus
A$.

To obtain our final algorithm, we will instead exploit the algebraic
relationship between $\mathrm{RM}[\mathbb{F},m,d]$ and its subcode
$\mathrm{RM}[\mathbb{F},m,d-1]$ to derive a _sufficient_ condition for every
$w\in A$ being $S$-good. Observe that if
$\mathsf{LD}[Z_{A},d-1]|_{S}=\mathrm{RM}[\mathbb{F},m,d-1]|_{S}$, then for
every $w\in A$ there is a $\hat{Z}_{w}\in\mathsf{LD}[Z_{A},d-1]$ such that
$p_{w}\ {:=}\ \delta_{w}-\hat{Z}_{w}$ satisfies $p_{w}(w)=1$ and
$p_{w}(\vec{\alpha})=0$ for all $\vec{\alpha}\in S$. It follows that all $w\in
A$ are $S$-good, as we can set $q_{w}=p_{w}\cdot\delta_{w}$.

Thus, our efficient test for whether $A$ contains any $S$-bad point is as
follows: compute bases for $\mathsf{LD}[Z_{A},d-1]|_{S}$ and
$\mathrm{RM}[\mathbb{F},m,d-1]|_{S}$, and output “no” if they are of the same
dimension; otherwise output “maybe”. By the above discussion, this test does
not have any false negatives; however, there may be false positives. Provided
there are not too many false positives, this does not cause a problem (we can
either include them in $W$ or perform an extra test to filter them out). We
bound the number of false positives by noting that if the test says “maybe”,
this in fact means that there exists an “$S$-bad” point in $A$ with respect to
polynomials of degree $d-1$. By [AW09], provided $d\geq 2$, there are at most
$|S|$ such points.

###  2.4 Local simulation of subcube sums of LDEs

So far, we have built a simulator that can answer arbitrary queries to our
sumcheck PCP $\Pi$, provided those queries lie within the set $\\{0,1\\}^{\leq
m}\cup\mathbb{F}^{m}$, handling the combinatorial structure on the hypercube
and the algebraic, pseudorandom algebraic structure outside of it. In this
final part of the overview, we outline how this simulator can be extended to
handle all queries; i.e., queries in the set $\mathbb{F}^{\leq m}$.

To do this, it suffices to show that the code $\Sigma\mathrm{RM}$ admits a
locally-simulatable encoding, where
$\Sigma\mathrm{RM}[\mathbb{F},m,d]=\\{\Sigma[P]:P\in\mathrm{RM}[\mathbb{F},m,d]\\}$
and $\Sigma[P]$ is defined as in Eq. 2 (where $(c_{1},\ldots,c_{i})$ now
ranges over $\mathbb{F}^{i}$). Specifically, we show that the following
encoding function is locally simulatable:

  * $\mathsf{ENC}_{\Sigma\mathrm{RM}}^{d}(\Sigma[f]):$

    1. 1.

Sample $\hat{f}$ uniformly at random from $\mathsf{LD}[f,d]$.

    2. 2.

Output $\Sigma[\hat{f}]$.

Note that the _message_ (input to $\mathsf{ENC}_{\Sigma\mathrm{RM}}$) is
$\Sigma[f]$, even though $\mathsf{ENC}_{\Sigma\mathrm{RM}}$ operates only on
$f$. This is necessary for local simulation, since individual locations in
$\Sigma[\hat{f}]$ depend on partial sums of $f$ which cannot be computed from
few queries to $f$ itself.

We would like to follow the strategy from the previous section: given a set
$S\subseteq\mathbb{F}^{\leq m}$ on which we want to simulate
$\mathsf{ENC}_{\Sigma\mathrm{RM}}(\Sigma[f])$, compute the set of all “bad”
points $W\subseteq\\{0,1\\}^{\leq m}$, i.e., $w\in W$ if
$\mathsf{ENC}_{\Sigma\mathrm{RM}}(\Sigma[f])|_{S}$ conveys information about
$\Sigma[f](w)$. Unfortunately, unlike in the “plain” Reed–Muller case, it is
not clear how to even bound the _size_ of $W$, let alone compute it.

The issue here is that a single evaluation of $\Sigma[\hat{f}](\vec{\alpha})$
for $\vec{\alpha}\in\mathbb{F}^{i}$ depends on $\hat{f}(\vec{\beta})$ for
every point $\vec{\beta}\in\vec{\alpha}\times\\{0,1\\}^{m-i}$. Naively
applying the lemma of [AW09] to this set of points yields a set
$W\subseteq\\{0,1\\}^{m}$ of size $2^{m-i}$. To bound $|W|$ by a polynomial,
we must therefore crucially make use of the fact that making a few queries to
$\Sigma[\hat{f}]$ can reveal only a few (possibly large) _partial sums_ of
$\hat{f}$ — which we can hope to deduce from a small number of queries to
$\Sigma[f]$.

To achieve this we will give a _decomposition_ of $\Sigma\mathrm{RM}$ as a
sequence of $\mathrm{RM}$ codes on different numbers of variables, “tied
together” with constraints that enforce summation structure. In more detail,
let $T\subseteq\mathbb{F}^{\leq m}$ be a set with the following special
structure, which we call “closed”: if $(s_{1},\ldots,s_{i})\in S$, then its
“parent” $(s_{1},\ldots,s_{i-1})$ and its “siblings”
$(s_{1},\ldots,s_{i-1},0)$ and $(s_{1},\ldots,s_{i-1},1)$ are also in $S$. The
set $\\{0,1\\}^{\leq m}$ is closed; it is also easy to see that any set $T$
can be made closed by adding at most $3m|T|$ points. We prove the following
theorem about the structure of restrictions of $\Sigma\mathrm{RM}$ to closed
sets $T$:

######  Theorem 2.1 (Informally stated, see Theorem 6.5).

For any closed set $T$, any constraint
$z\in(\Sigma\mathrm{RM}[\mathbb{F},m,d]|_{T})^{\perp}$ lies in the span of the
following two types of constraint:

  * •

_summation constraints_ , which ensure that
$\Sigma[\hat{f}](t_{1},\ldots,t_{i})=\Sigma[\hat{f}](t_{1},\ldots,t_{i},0)+\Sigma[\hat{f}](t_{1},\ldots,t_{i},1)$
for $(t_{1},\ldots,t_{i})\in T$, $i<m$; and

  * •

_low-degree constraints_ , which are given by, for each $i$, the $i$-variate
Reed–Muller constraints on the set $T_{i}\ {:=}\ T\cap\mathbb{F}^{i}$; i.e.,
$(\mathrm{RM}[\mathbb{F},i,d]|_{T_{i}})^{\perp}$.

If we take $T=\\{0,1\\}^{\leq m}\cup S$, then
$T_{i}=\\{0,1\\}^{i}\cup(S\cap\mathbb{F}^{i})$ (assuming $S$ is closed). Using
this decomposition, we show that we can take as the “bad” set $W\ {:=}\
\bigcup_{i=1}^{m}W_{i}$, where $W_{i}$ is the set of
$(S\cap\mathbb{F}^{i})$-bad points in $\mathrm{RM}[\mathbb{F},i,d]$. Each
$W_{i}$ can be computed efficiently using the algorithm described in Section
2.3.

We conclude by giving some brief intuition on how we prove Theorem 2.1. We
show that any constraint $z$ supported on $T_{i}\cup T_{i+1}\cup\cdots\cup
T_{m}$ can be “flattened” into a constraint supported on $T_{i}$ only. Such
constraints belong to $(\mathrm{RM}[\mathbb{F},i,d]|_{T_{i}})^{\perp}$. We
then use a dimension-counting argument to show that these, augmented with the
summation constraints, span
$(\Sigma\mathrm{RM}[\mathbb{F},m,d]|_{T})^{\perp}$.

##  3 Preliminaries

For a vector $\vec{a}\in\Sigma^{i}$, we denote by $\ell(\vec{a})$ the _number
of entries_ in $\vec{a}$, i.e. $\ell(\vec{a})=i$. Throughout, $\mathbb{F}$ is
a finite field. For two vectors $x,y\in\mathbb{F}^{n}$, we denote the dot
product by $x\cdot y\ {:=}\ \sum_{i=1}^{n}x_{i}y_{i}$. For sets $A,B$, we
denote by $A\sqcup B$ the _disjoint union_ of $A$ and $B$.

Algorithms. We write $\mathcal{A}^{\pi}(x)$ to denote the output of
$\mathcal{A}$ when given input $x$ (explicitly) and oracle access to $\pi$. We
use the abbreviation PPT to denote probabilistic polynomial-time. We generally
omit the internal randomness of an algorithm from probability statements, that
is, we write $\Pr[\mathcal{A}(x)=0]$ to mean
$\Pr_{r\leftarrow\\{0,1\\}^{n}}[\mathcal{A}(x;r)=0]$.

Polynomials. For $d\in\mathbb{N}$, we write $\mathbb{F}^{\leq
d}[X_{1},\ldots,X_{m}]$ for the ring of polynomials in $m$ variables over
$\mathbb{F}$ of individual degree $d$. For
$\vec{d}=(d_{1},\dots,d_{m})\in\mathbb{N}^{m}$, we use
$\mathbb{F}^{\leq\vec{d}}[X_{1},\ldots,X_{m}]$ to denote the ring of
polynomials in $m$ variables over $\mathbb{F}$ of degree $d_{i}$ in $X_{i}$
for each $i\in[m]$.

Low-degree extensions. Given a function $f\colon A_{1}\times\dots\times
A_{m}\to\mathbb{F}$, $A_{1},\ldots,A_{m}\subseteq\mathbb{F}$, we denote the
set of all low-degree extensions of $f$ by $\mathsf{LD}_{\vec{d}}[f]\ {:=}\
\\{p\in\mathbb{F}^{\leq\vec{d}}[X_{1},\ldots,X_{m}]:p(x)=f(x)~{}\forall x\in
A_{1}\times\dots\times A_{m}\\}$.

Lagrange polynomials. Let $\mathbb{F}$ be a field, and let $m\in\mathbb{N}$.
Given $S_{1},\dots S_{m}\subseteq\mathbb{F}$ and a point $w\in
S_{1}\times\dots\times S_{m}$, we define the _Lagrange interpolating
polynomial for $\mathcal{S}$ and $w$_ to be

$L_{\mathcal{S},w}(x)\ {:=}\ \prod_{i=1}^{m}\prod_{z\in
S_{i}\setminus\\{w_{i}\\}}\frac{x_{i}-z_{i}}{w_{i}-z_{i}}\enspace,$

where denote $\mathcal{S}\ {:=}\ S_{1}\times\dots\times S_{m}$.
$L_{\mathcal{S},w}$ is of individual degree $|S_{i}|-1$ in its $i$-th
variable.

######  Fact 3.1.

The set of Lagrange interpolators $\\{L_{\mathcal{S},w}\\}_{w\in\mathcal{S}}$
form a basis for the space $\mathbb{F}^{\leq\vec{d}}[X_{1},\ldots,X_{m}]$
where $\vec{d}\ {:=}\ (|S_{1}|-1,\dots,|S_{m}|-1)$.

Vanishing functions. Given a subset $S\subseteq\mathbb{F}$ we denote the
function which is vanishing on $S$ by $\mathcal{Z}_{S}(x)\ {:=}\ \prod_{s\in
S}(x-s)$.

Vector reversal. For a vector $\vec{x}=(x_{1},x_{2},\ldots,x_{n})$, we denote
by $\vec{x}_{\mathsf{rev}}$ the _reversed_ vector
$(x_{n},x_{n-1},\ldots,x_{1})$.

###  3.1 Coding theory

Let $\Sigma$ an alphabet and let $\ell\in\mathbb{N}$. A _code_ $C$ is a subset
$C\subseteq\Sigma^{\ell}$. Given two strings $x,y\in\Sigma^{n}$, we denote the
Hamming distance between $x$ and $y$ by $\Delta(x,y)\ {:=}\
\left|\\{i\in[n]:x_{i}\neq y_{i}\\}\right|$. We say that a vector $x$ is
$\varepsilon$-far from a set $S\subseteq\Sigma^{n}$ if $\min_{y\in
S}\Delta(x,y)/n\geq\varepsilon$.

######  Definition 3.2.

Given a function $w\colon D\to\mathbb{F}$ and a subset $I\subseteq D$, we
denote by $w|_{I}$ the restriction of $w$ to $I$, that is the function
$w|_{I}\colon I\to\mathbb{F}$ such that $w(x)=w|_{I}(x)$ for all $x\in I$.

######  Definition 3.3.

Given a linear code $C\subseteq\mathbb{F}^{D}$ and a subset $I\subseteq D$, we
denote by $C|_{I}$ the code consisting of codewords from $C$ restricted to
$I$, that is

$C|_{I}=\\{w|_{I}:w\in C\\}\enspace.$

Note that $C|_{I}$ is itself a linear code, as it is a linear subspace of
$\mathbb{F}^{I}$.

Linear codes. Let $\mathbb{F}$ be a finite field. A code
$C\colon\mathbb{F}^{k}\to\mathbb{F}^{\ell}$ is _linear_ if it is an
$\mathbb{F}$-linear map from $\mathbb{F}^{k}$ to $\mathbb{F}^{\ell}$.

Reed-Muller codes and low-degree extensions. The Reed-Muller (RM) code is the
code consisting of evaluations of multivariate low-degree polynomials over a
finite field.

######  Definition 3.4.

Given a field $\mathbb{F}$, a positive integer $m$, and a degree vector
$\vec{d}=(d_{1},\dots,d_{m})\in\mathbb{N}^{m}$, we denote by
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$ the code of evaluations over
$\mathbb{F}^{m}$ of polynomials in
$\mathbb{F}^{\leq\vec{d}}[X_{1},\ldots,X_{m}]$. For $d\in\mathbb{N}$,
$\mathrm{RM}[\mathbb{F},m,d]\ {:=}\ \mathrm{RM}[\mathbb{F},m,(d,\ldots,d)]$.

Zero and sum codes. A _zero code_ is a subcode of a linear code that is zero
on a given subset.

######  Definition 3.5 (Zero codes).

Given a $C\subseteq\mathbb{F}^{D}$, and $S\subseteq D$, we define the _zero
code_

$\mathbf{Z}_{S}(C)=\\{w\in C:w|_{S}=\vec{0}\\}.$

A _sum code_ is the extension of a linear code obtained by appending all sums
of entries over a given subdomain.

######  Definition 3.6 (Sum codes).

For a product set $\mathcal{A}\ {:=}\ A_{1}\times\cdots\times A_{m}$, we
define $\mathcal{A}_{i}\ {:=}\ A_{1}\times A_{2}\times\cdots\times A_{i}$ and
$\mathcal{A}_{>i}\ {:=}\ A_{i+1}\times\cdots\times A_{m}$; $\mathcal{A}_{0}\
{:=}\ \\{\bot\\}$. We denote $\bar{\mathcal{A}}\ {:=}\
\cup_{i=0}^{m}\mathcal{A}_{i}$.

Given a code $C\subseteq\mathbb{F}^{D}$ where $D=D_{1}\times\cdots\times
D_{m}$ and $\mathcal{A}\subseteq D$, we define the _sum code_
$\Sigma_{\mathcal{A}}C\subseteq\mathbb{F}^{\bar{D}}$ to be the code consisting
of all of the subcube sums over $\mathcal{A}$ of the codewords in $C$. That
is,

$\Sigma_{\mathcal{A}}C\ {:=}\ \\{\Sigma_{\mathcal{A}}[w]:w\in C\\}$

where $\Sigma_{\mathcal{A}}[w]\colon\mathbb{F}^{D}\to\mathbb{F}^{\bar{D}}$ is
given by

$\Sigma_{\mathcal{A}}[w](\vec{x})\ {:=}\
\sum_{\vec{y}\in\mathcal{A}_{>\ell(\vec{x})}}w(\vec{x},\vec{y})~{}.$

If $D=\mathcal{A}$, we will typically omit $\mathcal{A}$ from the notation
(i.e., we write $\Sigma C$, $\Sigma[w]$).

###  3.2 Linear-algebraic claims

We will make use of the following simple linear-algebraic algorithms and
facts.

######  Claim 3.7.

Let $U\leq\mathbb{F}^{n}$ be a vector space. There is a polynomial-time
algorithm which, given a basis for $U$, computes a basis for $U^{\perp}$.

######  Claim 3.8.

Let $U\leq\mathbb{F}^{n},V\leq\mathbb{F}^{m}$ be vector spaces. There is a
polynomial-time algorithm which, given a linear map $M\in\mathbb{F}^{m\times
n}$ such that $\\{Mu:u\in U\\}=V$ and basis $B\in\mathbb{F}^{n\times k}$ for
$U^{\perp}$, outputs a basis for $V^{\perp}$.

###### Proof.

Use 3.7 to compute a basis $B^{\prime}\in\mathbb{F}^{n\times(n-k)}$ for $U$.
Then compute $A=MB^{\prime}\in\mathbb{F}^{m\times(n-k)}$; we have that
$V=\operatorname{colspan}(A)$ by assumption on $M$. Compute a basis for $V$
from $A$ by Gaussian elimination, and from this a basis for $V^{\perp}$ by
3.7. ∎

######  Claim 3.9.

Let $T:V\to W$ be a linear map. If $v\sim\mathcal{U}(V)$, then
$T(v)\sim\mathcal{U}(T(V))$.

###### Proof.

We have that

$\displaystyle\Pr_{v\leftarrow V}[T(v)=w]=\Pr_{v\leftarrow
V}[v\in\ker(T)+w]=\frac{|\ker(T)|}{|V|}=\frac{1}{|T(V)|}.$

∎

######  Definition 3.10.

Let $(D,<)$ be an ordered domain. For a vector $v\colon D\to\mathbb{F}$, we
define $\lambda(v)\ {:=}\ \min\\{i\in D:v(i)\neq 0\\}$, where the minimum is
taken with respect to $<$. A sequence of vectors $v_{1},\ldots,v_{n}\colon
D\to\mathbb{F}$ is in _echelon form_ if, for all $i<j$,
$\lambda(v_{i})<\lambda(v_{j})$, and any all-zero vectors are at the end of
the sequence.

It is a straightforward consequence of Gauss–Jordan elimination that every
subspace of $(D\to\mathbb{F})$ has a basis in echelon form. Conversely, a
sequence of vectors in echelon form (not containing the all-zero vector) forms
a linearly independent set.

######  Definition 3.11.

Let $(R,<_{R})$ and $(C,<_{C})$ be ordered domains and let
$A\in\mathbb{F}^{R\times C}$. The _leading entry_ of a row
$w\in\mathbb{F}^{C}$ of $A$ is $w(\lambda(w))$, i.e., the first non-zero entry
in that row, with respect to the ordering $<_{C}$.

######  Definition 3.12.

Let $(R,<_{R})$ and $(C,<_{C})$ be ordered domains. A matrix
$A\in\mathbb{F}^{R\times C}$ is said to be in _reduced row echelon form_ if
(i) the columns of $A$, listed in increasing order by their indices with
respect to $<_{C}$ are in row echelon form (with respect to $<_{D}$);  (ii)
all leading entries are 1; and  (iii) all entries in the same column as a
leading entry are 0.

Every matrix can be converted to reduced row echelon form via Gauss-Jordan
elimination, and moreover, the resulting matrix is unique. We will often
represent systems of linear equations in their matrix form. We refer to
variables with a leading entry in their column of the reduced row echelon form
matrix as _leading variables_ , and the remaining variables as _free
variables_.

###  3.3 The combinatorial nullstellensatz

The combinatorial nullstellensatz, due to Alon [Alo99], is a powerful tool in
combinatorial number theory. It is stated as follows.

######  Lemma 3.13.

Let $\mathbb{F}$ be an arbitrary field, and let $f$ be a polynomial in
$\mathbb{F}[X_{1},\ldots,X_{n}]$. Let $S_{1},\ldots,S_{n}$ be nonempty subsets
of $\mathbb{F}$ and define $\mathcal{Z}_{S_{i}}(x_{i})=\prod_{s\in
S_{i}}(x_{i}-s)$. If $f$ vanishes over all the common zeros of
$\mathcal{Z}_{S_{1}},\ldots,\mathcal{Z}_{S_{n}}$ (that is, if
$f(s_{1},\ldots,s_{n})=0$ for all $s_{i}\in S_{i}$), then there are
polynomials $h_{1},\ldots,h_{n}\in\mathbb{F}[X_{1},\ldots,X_{n}]$ so that
$\deg(h_{i})\leq\deg(f)-\deg(\mathcal{Z}_{S_{i}})$ so that

$f=\sum_{i=1}^{n}h_{i}\mathcal{Z}_{S_{i}}\enspace.$

##  4 Locally simulatable encodings

In this section we introduce the notion of locally simulatable encodings.
First, we define randomised encoding functions, which are randomised mappings
from a message space $\mathcal{M}$ into a code $\mathcal{C}$.

######  Definition 4.1 (Randomised encoding function).

Let $\Sigma$ be an alphabet, $S,D$ be sets, and
$\mathcal{M}\subseteq\Sigma^{S},\mathcal{C}\subseteq\Sigma^{D}$ be the
_message space_ and _code space_ , respectively. A _randomised encoding
function_ is a random variable $\mathsf{ENC}$ taking values in
$\mathcal{M}\to\mathcal{C}$.

Next, we define what it means for a randomised encoding function to be locally
simulatable. At a high level, we require that the (conditional) distribution
of any local view of the encoding can be efficiently simulated using only a
local view of the message.

######  Definition 4.2 (Locally simulatable encoding).

Let $\mathsf{ENC}\colon\mathcal{M}\to\mathcal{C}$ be a randomised encoding
function, let $t\colon\mathbb{N}\to\mathbb{N}$ and let
$\ell\colon\mathbb{N}\to\mathbb{N}$. We say that $\mathsf{ENC}$ is _$(t,\ell)$
-locally simulatable_ if there is a probabilistic algorithm $\mathcal{S}$,
called a _local simulator_ , which receives oracle access to a message
$m\in\mathcal{M}$, a query-answer set $T\in(D\times\Sigma)^{n}$ and a new
query $\alpha\in D$, runs in time $t(n)$ and makes at most $\ell(n)$ queries
to $m$, satisfying:

$\Pr[\mathcal{S}^{m}(T,\alpha)=\beta]=\Pr\left[\mathsf{ENC}(m)_{\alpha}=\beta~{}|~{}\mathsf{ENC}(m)_{x}=y~{}\forall(x,y)\in
T\right],$

for all $m\in\mathcal{M},\alpha\in D,\beta\in\Sigma$, and for all $T$ such
that there exists $c\in\mathsf{supp}(\mathsf{ENC}_{m})$ with $c_{x}=y$ for all
$(x,y)\in T$.

To give a sense of the definition, we consider two examples.

######  Example 4.3.

The randomised encoding function which maps $m\in\mathbb{F}^{S}$,
$S\subseteq\mathbb{F}$, to the evaluation of a random univariate polynomial
$p$ over $\mathbb{F}$ of degree $2(|S|-1)$ such that $p(x)=m(x)$ for all $x\in
S$, is $(\mathrm{poly}(n,d,\log|\mathbb{F}|),n)$-locally simulatable. Indeed,
for $I\subseteq\mathbb{F}$, $|I|\leq|S|-1$, $p|_{I}$ is distributed as
$(m(x))_{x\in I\cap S}\|(\mathcal{U}(\mathbb{F}))_{x\in I\setminus S}$. For
$|I|\geq|S|$, the simulator $\mathcal{S}$ can simply fully determine $m$ and
directly conditionally sample $p$.

######  Example 4.4.

The encoding function which maps $m\in\mathbb{F}^{S}$, $S\subseteq\mathbb{F}$,
to the evaluation of the _unique_ univariate polynomial $p$ over $\mathbb{F}$
of degree $|S|-1$ such that $p(x)=m(x)$ for all $x\in S$, is _not_
$(t,\ell)$-locally simulatable unless $\ell(n)\geq|S|$ for all $n>0$. Indeed,
determining $p(x)$ for $x\in\mathbb{F}\setminus S$ requires knowledge of the
entire message $m$.

###  4.1 Linear randomised encoding functions

In this work we will focus on a special family of randomised encoding
functions, for which the randomised encoding is given by appending a random
vector to the message, and then applying a linear function.

######  Definition 4.5 (Linear randomised encoding function).

We say that $\mathsf{ENC}\colon\mathcal{M}\to\mathcal{C}$ is a _linear
randomised encoding function_ if $\Sigma=\mathbb{F}$ for some finite field
$\mathbb{F}$, and $\mathsf{ENC}(m)$ is distributed as $\mathsf{ENC}(m;\mu)$
where $\mu\sim\mathcal{U}(\mathbb{F}^{r})$ and
$\mathsf{ENC}\colon\mathcal{M}\times\mathbb{F}^{r}\to\mathcal{C}$ is a
(deterministic) linear function (of both message and randomness).

That is, we use $\mathsf{ENC}$ to refer to both the fixed encoding function
and the resulting random variable.

Linear randomised encodings have certain structural properties that make them
easier to work with. One important property of linear randomised encodings is
that the distribution of $\mathsf{ENC}(m)|_{I}$ can be characterised as the
solution space of an affine system. An $\ell$-constraint locator is an
algorithm which outputs a description of this system, defined as follows.

######  Definition 4.6.

Let $\mathsf{ENC}\colon\mathcal{M}\to\mathcal{C}$ be a linear randomised
encoding function, and let $\ell\colon\mathbb{N}\to\mathbb{N}$. We say that an
algorithm $\mathsf{CL}$ is an _$\ell$ -constraint locator for $\mathsf{ENC}$_
if, for every subdomain $I\subseteq D$, it satisfies

$\mathsf{CL}(I)=(R,Z),$

where $R\subseteq S$ and $Z\in\mathbb{F}^{k\times(R\sqcup I)}$ are such that
$|R|=\ell(|I|)$, and for every message $m\in\mathcal{M}$ and
$\vec{\beta}\in\mathbb{F}^{I}$,
$(m|_{R},\vec{\beta})^{T}\in\ker(Z)\subseteq\mathbb{F}^{R\sqcup I}$ if and
only if there exists randomness $\mu\in\mathbb{F}^{r}$ such that:

$\mathsf{ENC}(m;\mu)|_{I}=\vec{\beta}.$

Our notion of an $\ell$-constraint locator generalises the notion of a
“constraint detector” introduced in [BCFGRS17]. A constraint detector for a
linear code $C\subseteq\mathbb{F}^{D}$ takes as input a subdomain $I\subseteq
D$ and outputs a matrix representing all linear relations that hold between
codewords in $C|_{I}$. Setting the randomised encoding function for our
$\ell$-constraint locator to be the uniform distribution over all codewords in
$C$, we recover the definition of a constraint detector.

######  Definition 4.7 (Constraint detector).

Let $\mathcal{C}\subseteq\mathbb{F}^{D}$ be a linear code. A _constraint
detector for $\mathcal{C}$_ is a $0$-constraint locator for
$\mathsf{ENC}_{\mathcal{C}}\colon\varnothing\to\mathcal{C}$, the linear
randomised encoding function given by
$\mathsf{ENC}_{\mathcal{C}}\sim\mathcal{U}(\mathcal{C})$.

Given an efficient constraint locator, it is straightforward to construct a
local simulator.

######  Claim 4.8.

Let $\mathsf{ENC}\colon\mathcal{M}\to\mathcal{C}$ be a linear randomised
encoding with an $\ell$-constraint locator running in time $t$. Then
$\mathsf{ENC}$ is $(t,\ell)$-locally simulatable.

######  Construction 4.9.

A local simulator $\mathcal{S}$ for a linear randomised encoding function
$\mathsf{ENC}\colon\mathbb{F}^{S}\to\mathbb{F}^{D}$ given an $\ell$-constraint
locator $\mathsf{CL}$ for $\mathsf{ENC}$.
$\mathcal{S}_{\mathsf{ENC}}^{m}(T,\alpha)$: 1. Set
$(R,Z)=\mathsf{CL}(\mathsf{supp}(T)\cup\\{\alpha\\})$. 2. For each $\gamma\in
R$, query the message and set $m_{\gamma}\ {:=}\ m(\gamma)$. 3. If there
exists a row $z\in\mathbb{F}^{R\cup\mathsf{supp}(T)\cup\\{\alpha\\}}$ of the
matrix $Z$ with $z(\alpha)\neq 0$, output
$\beta\ {:=}\
-\frac{1}{z(\alpha)}\sum_{x\in\mathsf{supp}(T)}y_{x}z(x)+\sum_{x\in
R}m_{x}z(x)$, where $(x,y_{x})\in T$. 4. Otherwise, output
$\beta\leftarrow\mathbb{F}$.

###### Proof.

First we introduce some notation. Denote $p_{\beta}\ {:=}\
\Pr[\mathsf{ENC}(m)_{\alpha}=\beta\mid\mathsf{ENC}(m)_{x}=y~{}\forall(x,y)\in
T]$. Denote $I\ {:=}\ \mathsf{supp}(T)\cup\\{\alpha\\}$ and denote $\kappa\
{:=}\ -\frac{1}{z(\alpha)}\sum_{x\in\mathsf{supp}(T)}y_{x}z(x)+\sum_{x\in
R}m_{x}z(x)$. Define the vector $\vec{y}\in\mathbb{F}^{\mathsf{supp}(T)}$ to
be the vector consisting of values $y_{x}$ for each $(x,y_{x})\in T$.

We will break the proof into two parts, corresponding to the two possibilities
for the output of the construction in Step 3 and Step 4. First, we show that
if there exists a row $z\in\mathbb{F}^{R\cup\mathsf{supp}(T)\cup\\{\alpha\\}}$
of the matrix $Z$ with $z(\alpha)\neq 0$ (as in Step 3), then $p_{\beta}=1$ if
$\beta=\kappa$ and $p_{\beta}=0$ otherwise. If there exists such a row, then
the vector $(\beta,\vec{y},m|_{R})\in\ker(Z)$ if and only if $\beta=\kappa$.
By the correctness of $\mathsf{CL}$, $(\beta,\vec{y},m|_{R})\in\ker(Z)$ if and
only if there exists randomness $\mu$ such that
$\mathsf{ENC}(m;\mu)|_{I}=(\beta,\vec{y})$. So for all randomness
$\mu\in\mathbb{F}^{r}$, $\mathsf{ENC}(m;\mu)|_{I}=(\beta,\vec{y})$ if and only
if $\beta=\kappa$; hence $p_{\beta}=1$ if $\beta=\kappa$ and $p_{\beta}=0$
otherwise.

Second, we show that if there does not exist a row $z$ with $z(\alpha)\neq 0$
(as in Step 4), then $p_{\beta}=\frac{1}{|\mathbb{F}|}$, for all
$\beta\in\mathbb{F}$. For each $\beta\in\mathbb{F}$, consider the set of all
possible choices of randomness which agree with $T\cup(\alpha,\beta)$, that is
$Q_{\beta}\ {:=}\
\\{\mu\in\mathbb{F}^{r}:\mathsf{ENC}(m,\mu)|_{\\{\alpha\\}\cup\mathsf{supp}(T)}=(\beta,\vec{y})\\}$.
We will show that $|Q_{\beta}|=|Q_{\beta^{\prime}}|$ for each
$\beta,\beta^{\prime}\in\mathbb{F}$ by giving a bijection, which implies that
$p_{\beta}=\frac{1}{|\mathbb{F}|}$, since $\mu$ is chosen uniformly at random.

In this case, $(\beta,\vec{y},m|_{R})\in\ker(Z)$ for all $\beta\in\mathbb{F}$.
Then, by the correctness of $\mathsf{CL}$, for all $\beta\in\mathbb{F}$, there
exists randomness $\mu\in\mathbb{F}^{r}$ such that
$\mathsf{ENC}(m,\mu)|_{I}=(\beta,\vec{y})$, that is, $Q_{\beta}$ is non-empty
for each $\beta\in\mathbb{F}$. Let $\mu_{\beta}\in Q_{\beta}$ and let
$\mu_{\beta^{\prime}}\in Q_{\beta^{\prime}}$. It is easy to verify that the
map $M\colon Q_{\beta}\to Q_{\beta^{\prime}}$ defined by $M(\mu)\ {:=}\
\mu+(\mu_{\beta^{\prime}}-\mu_{\beta})$ is bijective, completing the proof. ∎

We prove that $\ell$-constraint locators satisfy a useful composition
property. That is, given constraint locators for encodings
$\mathsf{ENC}_{\text{in}}$ and $\mathsf{ENC}_{\text{out}}$, we can construct a
constraint locator for the composed encoding
$\mathsf{ENC}_{\text{out}}\circ\mathsf{ENC}_{\text{in}}$.

######  Claim 4.10.

Let
$\mathsf{ENC}_{\text{in}}\colon\mathbb{F}^{S}\to\mathbb{F}^{D_{\text{in}}}$
and
$\mathsf{ENC}_{\text{out}}\colon\mathbb{F}^{D_{\text{in}}}\to\mathbb{F}^{D_{\text{out}}}$
admit $\ell_{\text{in}}$-constraint location and
$\ell_{\text{out}}$-constraint location respectively. Then
$\mathsf{ENC}_{\text{out}}\circ\mathsf{ENC}_{\text{in}}(M;\mu_{\text{in}},\mu_{\text{out}})\
{:=}\
\mathsf{ENC}_{\text{out}}(\mathsf{ENC}_{\text{in}}(m;\mu_{\text{in}});\mu_{\text{out}})$
admits $(\ell_{\text{in}}\circ\ell_{\text{out}})$-constraint location.

######  Construction 4.11.

A constraint locator $\mathsf{CL}_{*}$ for $\mathsf{ENC}^{*}$, which receives
oracle access to the message $m$ and is given constraint locators
$\mathsf{CL}_{\text{in}}$ and $\mathsf{CL}_{\text{out}}$ for
$\mathsf{ENC}_{\text{in}}$ and $\mathsf{ENC}_{\text{out}}$ respectively. It
receives as input a subdomain $I\subseteq D_{\text{out}}$.
$\mathsf{CL}_{*}(I)$: 1. Compute $(R_{\text{out}},Z_{\text{out}})\ {:=}\
\mathsf{CL}_{\text{out}}(I)$. 2. Compute $(R_{\text{in}},Z_{\text{in}})\ {:=}\
\mathsf{CL}_{\text{in}}(R_{\text{out}})$. 3. Define $Z_{*}$ to the
$(k_{\text{in}}+k_{\text{out}})\times(|I|+|R_{\text{out}}|+|R_{\text{in}}|)$
matrix defined as $Z_{*}\ {:=}\
\left(\begin{array}[]{ccc}Z_{\text{out}}|_{I}&Z_{\text{out}}|_{R_{\text{out}}}&\mathbf{0}\\\
\mathbf{0}&Z_{\text{in}}|_{R_{\text{out}}}&Z_{\text{in}}|_{R_{\text{in}}}\\\
\end{array}\right),$ where $k_{\text{in}}$ and $k_{\text{out}}$ are the number
of rows in $Z_{\text{in}}$ and $Z_{\text{out}}$ respectively. 4. Using
Gaussian elimination, compute a basis $\mathcal{B}$ for the space $V\ {:=}\
\ker(Z_{*})$. 5. Compute a basis $\mathcal{B}^{\prime}$ for the space
$(V|_{I\cup R_{\text{in}}})^{\perp}$, using 3.7 and 3.8. Define $Z$ to be the
matrix whose rows are the elements of $\mathcal{B}^{\prime}$. 6. Output
$(R_{\text{in}},Z)$.

###### Proof.

Let $m\in\mathbb{F}^{S}$, and denote $w_{m}\ {:=}\
\mathsf{ENC}_{\text{in}}(m;\mu_{\text{in}})$ and $c_{w}\ {:=}\
\mathsf{ENC}_{\text{out}}(w;\mu_{\text{out}})$.

By the correctness of $\mathsf{CL}_{\text{out}}$, it holds that
$\vec{\alpha}\in\mathbb{F}^{I}$ satisfies
$(\vec{\alpha},w|_{R_{\text{out}}})\in\ker(Z_{\text{out}})$ if and only if
there exists randomness $\mu_{\text{out}}$ such that for every message
$w\in\mathbb{F}^{D_{\text{in}}}$, $c_{w}|_{I}=\vec{\alpha}$. Similarly, we
have that $\vec{\beta}\in\mathbb{F}^{R_{\text{out}}}$ satisfies
$(\vec{\beta},m|_{R_{\text{in}}})\in\ker(Z_{\text{in}})$ if and only if there
exists randomness $\mu_{\text{in}}$ such that for every message
$m\in\mathbb{F}^{S}$, $w_{m}|_{R_{\text{out}}}=\vec{\beta}$.

Then by definition of $Z_{*}$ we must have that
$(\vec{\alpha},\vec{\beta},m|_{R_{\text{in}}})\in\ker(Z_{*})$ if and only if
there exists $\mu_{\text{out}},\mu_{\text{in}}$ such that for all messages
$m\in\mathbb{F}^{S}$, it holds that $w_{m}|_{R_{\text{out}}}=\vec{\beta}$ and
$c_{w_{m}}|_{I}=\vec{\alpha}$. Finally, as $Z$ is defined to be the matrix
whose rows are the elements of a basis for $(V|_{I\cup
R_{\text{in}}})^{\perp}=(\ker(Z_{*}|_{I\cup R_{\text{in}}}))^{\perp}$, we have
that $(\vec{\alpha},m|_{R_{\text{in}}})\in\ker(Z)$ if and only if there exists
randomness $\mu_{\text{in}},\mu_{\text{out}}$, for which
$\mathsf{ENC}^{*}(m;\mu_{\text{in}},\mu_{\text{out}})|_{I}=\vec{\alpha}$. ∎

Note that this claim does not seem to generalise to permit composition of
arbitrary locally simulatable encodings. Indeed, here we are implicitly using
the fact that a constraint locator allows efficient sampling of a random input
to $\mathsf{ENC}_{\text{out}}$ consistent with (the restriction to $I$ of) a
given output. For general locally simulatable encodings, such an algorithm may
not exist.

##  5 Constraint location for random low-degree extensions

In this section we construct an efficient constraint locator for random low-
degree extensions of a given function. In Section 5.1, we construct an
efficient constraint _detector_ (cf. Definition 4.7) for polynomials which are
zero on a given product set $\mathcal{S}$, i.e., for the code
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])$. In Section 5.2,
we use this constraint detector to construct a “decision” constraint locator
for random low-degree extensions, which accepts on inputs which are
constrained, and rejects on inputs which are unconstrained. In Section 5.3, we
efficiently reduce the task of (search) constraint location to the decision
version.

In order to state the main theorem of this section, we first define a
randomised encoding that maps a function $f$ to a random extension of
specified degree.

######  Definition 5.1.

Let $\mathsf{ENC}_{\mathrm{RM}(\vec{d},\mathcal{S})}$ to be the randomised
encoding function that maps $f\colon\mathcal{S}\to\mathbb{F}$, where
$\mathcal{S}\ {:=}\ S_{1}\times\dots\times S_{m}\subseteq\mathbb{F}^{m}$,
$d_{i}\geq 2(|S_{i}|-1)$ for all $i\in[m]$, to a random degree-$\vec{d}$
extension of $f$, i.e., a uniformly random element of
$\mathsf{LD}_{\vec{d}}[f]$.

Note the restriction that $|d_{i}|\geq 2(|S_{i}|-1)$; this is tight in the
case that $|S_{1}|=\cdots=|S_{m}|=2$. We prove the following theorem.

######  Theorem 5.2.

There is an $n$-constraint locator for
$\mathsf{ENC}_{\mathrm{RM}(\vec{d},\mathcal{S})}$ running in time
$\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$.

As a corollary, we obtain a local simulator for
$\mathsf{ENC}_{\mathrm{RM}(\vec{d},\mathcal{S})}$: that is, we obtain an
algorithm that can efficiently simulate a random low-degree extension of $f$
given oracle access to $f$.

######  Corollary 5.3.

$\mathsf{ENC}_{\mathrm{RM}(\vec{d},\mathcal{S})}$ is $(t,n)$-locally
simulatable for $t(n)=\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$.

###  5.1 A constraint detector for random low-degree extensions of the zero
function

We construct an efficient constraint detector for
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])$, where
$\mathcal{S}$ is a product set, and $\mathbf{Z}_{\mathcal{S}}(\cdot)$ denotes
the subcode consisting of codewords which are zero on $\mathcal{S}$. We shall
employ the following result, which is proved in [BCFGRS17].

######  Theorem 5.4.

There is a constraint detector $\mathsf{CD}_{\vec{d}}$ for
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$, running in time
$\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$.

We prove the following.

######  Lemma 5.5.

5.6 is a constraint detector for
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])$, running in time
$\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$.

######  Construction 5.6.

A constraint detector for
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])$, where
$\mathcal{S}\ {:=}\ S_{1}\times\dots\times S_{m}$, given a constraint detector
$\mathsf{CD}_{\vec{d}}$ for $\mathrm{RM}[\mathbb{F},m,\vec{d}]$. Receives as
input a subdomain $I\subseteq\mathbb{F}^{m}.$
$\mathsf{CD}_{\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])}(I)$:
1. For each $i\in[m]$, compute $Z_{i}\ {:=}\ \mathsf{CD}_{\vec{d_{i}}}(I)$
where $\vec{d_{i}}\ {:=}\ (d_{1},\dots,d_{i}-|S_{i}|,\dots,d_{m})$. 2. Define
the block diagonal matrix $Z^{\prime}\ {:=}\
\left(\begin{array}[]{cccc}Z_{1}&\mathbf{0}&\dots&\mathbf{0}\\\
\mathbf{0}&Z_{2}&\dots&\mathbf{0}\\\ \vdots&\vdots&\ddots&\vdots\\\
\mathbf{0}&\mathbf{0}&\dots&Z_{m}\end{array}\right)\enspace.$ 3. Using
Gaussian elimination, compute a basis $b_{1},\dots,b_{k}$ for
$\ker(Z^{\prime})$ and define $\mathcal{B}$ to be the $k\times|I|\cdot m$
matrix whose $i$-th row is $b_{i}$. 4. Define the $|I|\cdot m\times|I|$ matrix
$A_{I}$ to be the matrix whose $((\vec{\alpha},i),\vec{\gamma})$-entry is
$\mathcal{Z}_{S_{i}}(\alpha_{i})$ if $\vec{\alpha}=\vec{\gamma}$ and $0$
otherwise (where $\mathcal{Z}_{S_{i}}(x)\ {:=}\ \prod_{s\in S_{i}}(x-s)$). 5.
Compute $G\ {:=}\ (\mathcal{B}A_{I})^{T}$, an $|I|\times k$ matrix, which is a
generator matrix for
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}$. 6. Using
$G$, compute a parity check matrix $H$ for
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}$, and output
$H$.

###### Proof.

In order to prove that 5.6 is a constraint detector for
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])$, it suffices to
show that $G\ {:=}\ (\mathcal{B}A_{I})^{T}$ is a valid generator matrix for
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}$; i.e.,
$\mathrm{Im}(G)=\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}$.

We show that
$\mathrm{Im}(G)\subseteq\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}$
using the fact that
$\ker(Z^{\prime})=\prod_{i=1}^{m}\mathrm{RM}[\mathbb{F},m,\vec{d}_{i}]|_{I}$
(Theorem 5.4) and some linear algebra. We prove the reverse inclusion via the
combinatorial nullstellensatz (see Lemma 3.13).

Before we proceed, it will be very useful to write down an expression for an
individual entry of $G$. For $\vec{\beta}\in I,\ell\in[k]$, the
$(\vec{\beta},\ell)$-entry of $G$, which we will denote by
$G_{\ell}(\vec{\beta})$, is given by the expression

$G_{\ell}(\vec{\beta})=\sum_{i=1}^{m}b_{\ell}(i,\vec{\beta})\mathcal{Z}_{S_{i}}(\beta_{i}),$
(3)

where $b_{\ell}$ is the $\ell$-th basis element computed in Step 3 and
$\mathcal{Z}_{S_{i}}(X)\ {:=}\ \prod_{s\in S}(x-s)$. We now proceed with the
proof.

Correctness. We first show
$\mathrm{Im}(G)\subseteq\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}$.
Let $y\in\mathrm{Im}(G)$. Then, for some scalars
$a_{1},\dots,a_{k}\in\mathbb{F}$, and for each $\vec{\beta}\in I$, we can
write

$y(\vec{\beta})=\sum_{j=1}^{k}a_{j}G_{j}(\vec{\beta})=\sum_{j=1}^{k}a_{j}\sum_{i=1}^{m}b_{j}(i,\vec{\beta})\mathcal{Z}_{S_{i}}(\beta_{i})=\sum_{i=1}^{m}\mathcal{Z}_{S_{i}}(\beta_{i})\sum_{j=1}^{k}a_{j}b_{j}(i,\vec{\beta}),$

where the second equality follows from Eq. 3. We also know that
$b_{j}(i,\vec{X})\in\mathrm{RM}[\mathbb{F},m,\vec{d_{i}}]|_{I}$ for each
$j\in[k]$, and $i\in[m]$ because $b_{1},\dots,b_{k}$ is a basis for
$\ker(Z^{\prime})=\prod_{i=1}^{m}\mathrm{RM}[\mathbb{F},m,\vec{d}_{i}]|_{I}$.
Then by the linearity of $\mathrm{RM}[\mathbb{F},m,\vec{d_{i}}]$, we have that
for each $i\in[m]$, $\sum_{j=1}^{k}a_{j}b_{j}(i,\vec{X})\ {:=}\
R_{i}(\vec{X})\in\mathrm{RM}[\mathbb{F},m,\vec{d}_{i}]|_{I}$. Substituting
this into our expression for $y(\vec{\beta})$,

$y(\vec{\beta})=\sum_{i=1}^{m}R_{i}(\vec{\beta})\mathcal{Z}_{S_{i}}(\beta_{i}).$

Therefore $y\in\mathrm{RM}[\mathbb{F},m,\vec{d}]|_{I}$. As
$\mathcal{Z}(\beta_{i})=0$ for all $\beta_{i}\in S_{i}$ and $i\in[m]$, we have
that $y(\vec{\beta})=0$ for all $\vec{\beta}\in\mathcal{S}$, so
$y\in\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}$.

Now we show
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}\subseteq\mathrm{Im}(G)$.
Let
$\tilde{Z}\in\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{I}$.
Then by the combinatorial nullstellensatz (Lemma 3.13) there exists $\vec{R}\
{:=}\
(R_{1},\dots,R_{m})\in\prod_{i=1}^{m}\mathrm{RM}[\mathbb{F},m,\vec{d_{i}}]|_{I}$
such that

$\tilde{Z}(\vec{\beta})=\sum_{i=1}^{m}\mathcal{Z}_{S_{i}}(\beta_{i})R_{i}(\vec{\beta}),$

for all $\beta\in I$. As $\\{b_{1},\dots,b_{k}\\}$ is a basis for
$\prod_{i=1}^{m}\mathrm{RM}[\mathbb{F},m,\vec{d_{i}}]|_{I}$, we can write

$R_{i}(\vec{\beta})=\sum_{j=1}^{k}a_{j}b_{j}(i,\vec{\beta}),$

for some $a_{j}\in\mathbb{F}$. Then substituting into the previous expression
for $\tilde{Z}$ yields

$\tilde{Z}(\vec{\beta})=\sum_{i=1}^{m}\mathcal{Z}_{S_{i}}(\beta_{i})\sum_{j=1}^{k}a_{j}b_{j}(i,\vec{\beta})=\sum_{j=1}^{k}a_{j}\left(\sum_{i=1}^{m}b_{j}(i,\vec{\beta})\mathcal{Z}_{S_{i}}(\beta_{i})\right)=\sum_{j=1}^{k}a_{j}G_{j}(\vec{\beta}).$

Efficiency. 5.6 makes $m$ calls to $\mathsf{CD}_{\vec{d_{i}}}$, which runs in
time $\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$. In the remaining
steps, the algorithm performs only Gaussian elimination and matrix
multiplication of matrices whose sizes are polynomial in $|I|$ and $m$. ∎

###  5.2 The decision problem

Before stating the main result of this section we define the notion of a
constraint with respect to a linear code on a subset of its domain.

######  Definition 5.7.

Let $C\subseteq\mathbb{F}^{D}$ be a linear code. A subset $I\subseteq D$ is
_constrained with respect to $C$_ if there exists a nonzero vector
$z\in\mathbb{F}^{I}$ such that, for every codeword $w\in C$, $z\cdot w|_{I}=0$
(equivalently, if there exists $z\neq 0\in C^{\perp}$ with
$\mathsf{supp}(z)\subseteq I$); we refer to $z$ as a _constraint with respect
to $C$ on $I$_. We say that $I$ is _unconstrained with respect to $C$_ if it
is not constrained with respect to $C$.

We construct an algorithm $\mathsf{CheckConstraints}$ which, given as input a
(large) product set $\mathcal{S}$ and a polynomial-size set $I$, efficiently
determines whether $I\cup\mathcal{S}$ is constrained with respect to the Reed-
Muller code.

######  Lemma 5.8.

Let $\mathcal{S}\ {:=}\ S_{1}\times\cdots\times S_{m}$,
$I\subseteq\mathbb{F}^{m}$ and $\vec{d}=(d_{1},\ldots,d_{m})$ with
$d_{i}\geq|S_{i}|$ for all $i\in[m]$.
$\mathsf{CheckConstraints}_{\vec{d}}(I,\mathcal{S})$ outputs yes if and only
if and $I\cup\mathcal{S}$ is constrained with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$, and runs in time
$\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},|I|)$.

######  Construction 5.9.

An algorithm which efficiently determines whether a set $I\cup\mathcal{S}$ is
constrained with respect to the Reed–Muller code, given an efficient
constraint detector
$\mathsf{CD}_{\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])}(I)$
for $\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])$.
$\mathsf{CheckConstraints}_{\vec{d}}~{}(I,\mathcal{S})$: 1. Compute
$H=\mathsf{CD}_{\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])}(I\setminus\mathcal{S})$
(see 5.6). 2. If $H=0$, output no, otherwise output yes.

To prove the correctness of 5.9, we show an equivalence between constraint
detection for $\mathbf{Z}_{\mathcal{S}}(\mathrm{RM})$ and deciding whether
$I\cup\mathcal{S}$ is constrained with respect to $\mathrm{RM}$. In order to
do so, we shall require the following two properties of linear codes, whose
proofs we defer to Section A.1 and Section A.2.

######  Claim 5.10.

Let $C\subseteq\mathbb{F}^{D}$ be a linear code and let $I\subseteq D$. Then
$I$ is unconstrained with respect to $C$ if and only if for all $x\in I$ there
exists a codeword $w_{x}\in C$ satisfying  (i) $w_{x}(x)=1$and  (ii)
$w_{x}(y)=0$for all $y\in I\setminus\\{x\\}$.

######  Lemma 5.11.

Let $C\subseteq\mathbb{F}^{D}$ be a linear code, and let
$I,\mathcal{S}\subseteq D$. Suppose that $\mathcal{S}$ is unconstrained with
respect to $C$. Then $I\cup\mathcal{S}$ is constrained with respect to $C$ if
and only if $I\setminus\mathcal{S}$ is constrained with respect to
$\mathbf{Z}_{\mathcal{S}}(C)$.

As a corollary, we show an equivalence between constraints with respect to the
general Reed–Muller code and the Reed-Muller code fixed to be zero on a
product set.

######  Corollary 5.12.

Let $m\in\mathbb{N},\vec{d}\in\mathbb{N}^{m},I\subseteq\mathbb{F}^{m}$, let
$S_{1},\dots,S_{m}\subseteq\mathbb{F}$, be such that $|S_{i}|\leq d_{i}+1$ for
all $i\in[m]$, and denote $\mathcal{S}\ {:=}\ S_{1}\times\dots\times S_{m}$.
Then $I\cup\mathcal{S}$ is constrained with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$ if and only if $I\setminus\mathcal{S}$ is
constrained with respect to
$\mathbf{Z}_{\mathcal{S}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])$.

###### Proof.

By Lemma 5.11, it suffices to show that $\mathcal{S}$ is unconstrained with
respect to $\mathrm{RM}[\mathbb{F},m,\vec{d}]$. Consider, for each
$w\in\mathcal{S}$, the Lagrange polynomial
$L_{\mathcal{S},w}(\vec{X})\in\mathbb{F}^{\leq\vec{d}}[X_{1},\ldots,X_{m}]$.
As $|S_{i}|\leq d_{i}+1$ for all $i\in[m]$, the evaluation table of
$L_{\mathcal{S},w}(\vec{X})$ is a codeword in
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$, for each $w\in\mathcal{S}$. These
codewords satisfy $L_{\mathcal{S},w}(w)=1$ and $L_{\mathcal{S},w}(x)=0$ for
all $x\neq w\in\mathcal{S}$, so by 5.10, $\mathcal{S}$ is unconstrained with
respect to $\mathrm{RM}[\mathbb{F},m,\vec{d}]$. ∎

###### Proof of Lemma 5.8.

The correctness follows from Corollary 5.12 and the correctness of 5.6. The
runtime follows from the fact that 5.6 runs in time
$\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$. ∎

###  5.3 Search-to-decision reduction

In this section we show a reduction from constraint location of random low-
degree extensions (a search problem) to $\mathsf{CheckConstraints}$. Before
proving Theorem 5.2, we define what it means for a subset $I$ of the domain
$D$ of a code to _determine_ a point $x\in D$. We then prove some useful
technical lemmas.

######  Definition 5.13.

Let $C\subseteq\mathbb{F}^{D}$ be a linear code. We say that $I\subseteq D$
_determines_ $x\in D$ _with respect to $C$_ if $x\in I$ or there exists a
constraint $z$ with respect to $C$ on $I\cup\\{x\\}$ such that $z(x)\neq 0$.

The following lemma is central to our reduction. It shows that points which
are constrained with respect to the Reed–Muller code are determined with
respect to another Reed–Muller code of lower degree. Thus, in our algorithm,
it suffices to check the latter condition.

######  Lemma 5.14.

Let $m\in\mathbb{N},\vec{d}\ {:=}\
(d_{1},\dots,d_{m})\in\mathbb{N}^{m},I\subseteq\mathbb{F}^{m}$, let
$S_{1},\dots,S_{m}\subseteq\mathbb{F}$ and denote $\mathcal{S}\ {:=}\
S_{1}\times\dots\times S_{m}$. If there exists a constraint $z\colon
I\cup\mathcal{S}\to\mathbb{F}$ on $I\cup\mathcal{S}$ with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$ such that for some $w\in\mathcal{S}$,
$z(w)\neq 0$, then $w$ is determined by $I$ with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d^{\prime}}]$, where $\vec{d^{\prime}}\ {:=}\
(d_{1}-(|S_{1}|-1),\dots,d_{m}-(|S_{m}|-1))$.

###### Proof.

We proceed via contrapositive: if $w\in\mathcal{S}$ is not determined by $I$
with respect to $\mathrm{RM}[\mathbb{F},m,\vec{d^{\prime}}]$, then
$I\cup\mathcal{S}$ is unconstrained with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$.

Let $w\in\mathcal{S}$ be not determined by $I$ with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d^{\prime}}]$. Then there exists
$p(\vec{X})\in\mathbb{F}^{\leq\vec{d^{\prime}}}[X_{1},\ldots,X_{m}]$ such that
(i) $p(w)=1$and  (ii) $p(i)=0$for all $i\in I$.  Now define $q(\vec{X})\ {:=}\
p\cdot
L_{\mathcal{S},w}(\vec{X})\in\mathbb{F}^{\leq\vec{d}}[X_{1},\ldots,X_{m}]$,
where $L_{\mathcal{S},w}$ denotes the Lagrange polynomial. Note $q(\vec{X})$
satisfies:  (i) $q(w)=1$,  (ii) $q(x)=0$for all
$x\in\mathcal{S}\setminus\\{w\\}$ and  (iii) $q(i)=0$for all $i\in I$.  By
5.10 $I\cup\mathcal{S}$ is unconstrained with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$. ∎

We shall also need the following claim which defines the notion of an
_interpolating set_ and gives an algorithm for reducing an arbitrary subdomain
of a linear code to an interpolating set. We defer the proof of this claim to
Section A.3.

######  Claim 5.15.

Let $C\subseteq\mathbb{F}^{D}$ be a linear code which has an efficient
constraint detector. Given a subdomain $I\subseteq D$, there exists an
efficient algorithm, which computes an _interpolating set for $I$ with respect
to $C$_: a set $I^{\prime}\subseteq I$ such that:  (i) $I^{\prime}$is
unconstrained with respect to $C$; and  (ii) for every $\mathcal{S}\subseteq
D$ which is unconstrained with respect to $C$ and satisfies
$I\cap\mathcal{S}=\varnothing$, if there exists a constraint $z\colon
I\cup\mathcal{S}\to\mathbb{F}$ such that $z(s)\neq 0$ for some
$s\in\mathcal{S}$, then there exists a constraint $z^{\prime}\colon
I^{\prime}\cup\mathcal{S}\to\mathbb{F}$ such that $z^{\prime}(s)\neq 0$.

We will also require the following simple monotonicity property of
$\mathsf{CheckConstraints}$ (see 5.9).

######  Claim 5.16.

If $\mathsf{CheckConstraints}(I,\mathcal{S})=\textsf{yes}$ and
$\mathcal{S}\subseteq\mathcal{S}^{\prime}$, then
$\mathsf{CheckConstraints}(I,\mathcal{S}^{\prime})=\textsf{yes}$.

###### Proof.

Clear from Lemma 5.8. ∎

Before we give our reduction, we give a slight generalisation of Lemma 4.2
from [AW09]. Its proof is a relatively straightforward adaptation of the proof
of that lemma and is deferred to Section A.4.

######  Lemma 5.17.

Let $m\in\mathbb{N}$, let $I\subseteq\mathbb{F}^{m}$, let
$S_{1},\dots,S_{m}\subseteq\mathbb{F}$ and denote $\mathcal{S}\ {:=}\
S_{1}\times\dots\times S_{m}$. Set $\vec{d}\ {:=}\
(|S_{1}|-1,\dots,|S_{m}|-1)$. There exists a set $G_{I}\subseteq\mathcal{S}$
with $|G_{I}|\geq|\mathcal{S}|-|I|$, such that for all $g\in G_{I}$ there
exists a polynomial
$p_{g}(\vec{X})\in\mathbb{F}^{\leq\vec{d}}[X_{1},\ldots,X_{m}]$ satisfying

  1. (i)

$p_{g}(x)=0$ for all $x\in I\cup G_{I}\setminus\\{g\\}$ and

  2. (ii)

$p_{g}(g)=1$.

We are now ready to prove the main result of this section.

###### Proof of Theorem 5.2.

We give a reduction from constraint location to
$\mathsf{CheckConstraints}_{\vec{d}}$.

Reduction 1 Reduction from constraint location for
$\mathsf{ENC}_{\mathrm{RM}(\vec{d},\mathcal{S})}$ to
$\mathsf{CheckConstraints}_{\vec{d}}$ and a constraint detector
$\mathsf{CD}_{\vec{d}}$ for $\mathrm{RM}[\mathbb{F},m,\vec{d}\ {:=}\
(d_{1},\dots,d_{m})]$.

Set $\vec{d^{\prime}}\ {:=}\ (d_{1}-(|S_{1}|-1),\dots,d_{m}-(|S_{m}|-1))$.
$\mathrm{Search}(I,t,M\ {:=}\ (S_{i},\dots,S_{m}))$:

if $M=\bot$ then

Return $t$.

else

Set $T=\varnothing$.

for all $s\in S_{i}$ do

if $\mathsf{CheckConstraints}_{\vec{d^{\prime}}}(I,t\times\\{s\\}\times
S_{i+1}\times\dots\times S_{m})=\textsf{yes}$ then

Add $\mathrm{Search}(I,t\times\\{s\\},(S_{i+1},\dots,S_{m}))$ to $T$.

Return $T$.

Compute $I^{\prime}$ to be an interpolating set for $I$.
Compute $T\ {:=}\ \mathrm{Search}(I^{\prime},\bot,(S_{1},\dots,S_{m}))$.
Output $(T,\mathsf{CD}_{\vec{d}}~{}(I\cup T))$.

Correctness. First, we show that if $I\cup\mathcal{S}$ is unconstrained with
respect to $\mathrm{RM}[\mathbb{F},m,\vec{d}]$ then Reduction 1 outputs
$\bot$. In this case, as $T\subseteq\mathcal{S}$, $I\cup T$ is unconstrained
so $\mathsf{CD}_{\vec{d}}~{}(I\cup T)=\bot$, as required.

Now we consider the case where $I\cup\mathcal{S}$ is constrained with respect
to $\mathrm{RM}[\mathbb{F},m,\vec{d}]$. We show that if $s\in
S_{1}\times\dots\times S_{m}$ is constrained, then $s\in T$, where $T$ is the
output of Reduction 1. By inspection of Reduction 1 and 5.16, we see that
$s\in T$ if and only if
$\mathsf{CheckConstraints}_{\vec{d^{\prime}}}(I^{\prime},\\{s_{1}\\}\times\dots\times\\{s_{m}\\})=\textsf{yes}$.
If there exists a constraint $z\colon I\cup S\to\mathbb{F}$ with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$ with $z(s)\neq 0$, then by 5.15, there
exists a constraint $z^{\prime}\colon I^{\prime}\cup\mathcal{S}$ with respect
to $\mathrm{RM}[\mathbb{F},m,\vec{d}]$ with $z^{\prime}(s)\neq 0$. Further, by
Lemma 5.14, $s$ is determined by $I^{\prime}$ with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d^{\prime}}]$.

Lastly, $\mathsf{CD}_{\vec{d}}~{}(I\cup T)$ will output a basis for the space
of constraints on $I\cup T$, so the output is in the desired form.

Efficiency. We show that the reduction is efficient by bounding the number of
calls made to $\mathsf{CheckConstraints}_{\vec{d}}$. For $i\in[m]$, we say a
point $(s_{1},\dots,s_{i})\in S_{1}\times\dots\times S_{i}$ is _$i$
-accepting_ if
$\mathsf{CheckConstraints}_{\vec{d^{\prime}}}(I,\\{s_{1}\\}\times\dots\times\\{s_{i}\\}\times
S_{i+1}\times\dots\times S_{m})=\textsf{yes}$. Note that by correctness of
$\mathsf{CheckConstraints}$ and the fact that $I^{\prime}$ is unconstrained,
this means that a point $(s_{1},\dots,s_{i})\in S_{1}\times\dots\times S_{i}$
is $i$-accepting if and only if there exists $(s_{i+1},\dots,s_{m})\in
S_{i+1}\times\dots\times S_{m}$ such that $(s_{1},\dots,s_{m})$ is involved in
a non-zero constraint with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d^{\prime}}]$. For all $i\in[m]$, let $a_{i}$
denote the number of points which are $i$-accepting.

Now we count the number of calls our reduction makes to
$\mathsf{CheckConstraints}$ in terms of $a_{1},\dots,a_{m-1}$. Note that
regardless of the value of $I$, Reduction 1 makes $|S_{1}|$ calls to
$\mathsf{CheckConstraints}_{\vec{d^{\prime}}}$ at the beginning. Subsequently,
for each $i\in[m-1]$, Reduction 1 makes $a_{i}|S_{i+1}|$ many calls to
$\mathsf{CheckConstraints}_{\vec{d^{\prime}}}$. Overall, the total number of
calls that Reduction 1 makes to $\mathsf{CheckConstraints}_{\vec{d^{\prime}}}$
is:

$N=|S_{1}|+\sum_{i=1}^{m-1}a_{i}|S_{i+1}|.$

Now we bound the size of $a_{i}$ for each $i\in[m]$. As
$d_{i}^{\prime}\geq|S_{i}|-1$ for all $i\in[m]$, Lemma 5.17 implies that there
exists a set $G_{I}$ with $|G_{I}|\geq|\mathcal{S}|-|I|$, such that for all
$g\in G_{I}$ there exists a polynomial
$p_{g}(\vec{X})\in\mathbb{F}^{\leq\vec{d^{\prime}}}[X_{1},\ldots,X_{m}]$
satisfying  (i) $p_{g}(x)=0$for all $x\in I\cup G_{I}\setminus\\{g\\}$ and
(ii) $p_{g}(g)=1$.  Thus, by 5.10, at most $|I|$ many points in $\mathcal{S}$
are constrained by $I$ with respect to
$\mathrm{RM}[\mathbb{F},m,\vec{d^{\prime}}]$. In other words, $a_{i}\leq|I|$
for all $i\in[m-1]$. Therefore

$N\leq|S_{1}|+|I|\sum_{i=1}^{m-1}|S_{i+1}|.$

Thus, as each call to $\mathsf{CheckConstraints}$ takes time
$\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$, and $|S_{i}|$ is bounded
by a polynomial in $d_{i}$ for each $i$, we have that
$t(n)=\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$.

Finally, the fact that at most $|I|$ many points in $\mathcal{S}$ are
constrained implies that $\ell(n)=n$. ∎

##  6 Constraint location for subcube sums of random low-degree extensions

In this section we extend the efficient constraint locator of the previous
section to support queries to subcube sums. We begin by defining the
corresponding randomised encoding.

######  Definition 6.1.

Let $\mathcal{A}\ {:=}\ A_{1}\times\dots\times A_{m}\subseteq\mathbb{F}^{m}$.
We define
$\mathsf{ENC}_{\Sigma\mathrm{RM}(\vec{d},\mathcal{A})}\colon\Sigma_{\mathcal{A}}(\mathcal{A}\to\mathbb{F})\to(\mathbb{F}^{\leq
m}\to\mathbb{F})$ as the randomised encoding
$\mathsf{ENC}_{\Sigma\mathrm{RM}(\vec{d},\mathcal{A})}(\Sigma_{\mathcal{A}}[F])\sim\mathcal{U}(\Sigma_{\mathcal{A}}[\mathsf{LD}_{\vec{d}}{[F]}])$,
where $d_{i}\geq|A_{i}|-1$ for all $i\in[m]$.

That is, $\mathsf{ENC}_{\Sigma\mathrm{RM}(\vec{d},\mathcal{A})}$ encodes a
message
$\Sigma_{\mathcal{A}}[F]\in\Sigma_{\mathcal{A}}(\mathcal{A}\to\mathbb{F})$ by
first choosing a random degree-$\vec{d}$ extension $\hat{F}$ of $F$, and then
outputting the word $\Sigma_{\mathcal{A}}[\hat{F}]\colon\mathbb{F}^{\leq
m}\to\mathbb{F}$ obtained by augmenting $\hat{F}$ with partial sums over
$\mathcal{A}$ (see Definition 3.6). Note that the input to
$\mathsf{ENC}_{\Sigma\mathrm{RM}(\vec{d},\mathcal{A})}$ includes partial sums
of $F$; these are not necessary to define the encoding but are essential to
permit local simulation.

The main theorem of this section is the following.

######  Theorem 6.2.

There is a $(t,\ell)$-constraint locator for
$\mathsf{ENC}_{\Sigma\mathrm{RM}(\vec{d},\mathcal{A})}$, where
$\ell(n)=nm(m(a+1)+1)^{2}$, for $a\ {:=}\ \max_{i}|A_{i}|$ and
$t(n)=\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$.

We prove this theorem by giving, in Section 6.1, a local characterisation of
$\Sigma\mathrm{RM}$ in terms of the plain Reed–Muller code. We give our
construction based on this characterisation in Section 6.2.

###  6.1 Local characterisation of $\Sigma$RM

In this subsection we give a local characterisation of $\Sigma\mathrm{RM}$ in
terms of the plain Reed–Muller code. We define the code $\Sigma\mathrm{RM}$ as
follows.

######  Definition 6.3.

Define $\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}]\ {:=}\
\Sigma_{\mathcal{A}}\mathrm{RM}[\mathbb{F},m,\vec{d}]\subseteq(\mathbb{F}^{\leq
m}\to\mathbb{F})$.

Our local characterisation will hold for certain “nice” subsets of
$\mathbb{F}^{\leq m}$ which we call “$\mathcal{A}$-closed”.

######  Definition 6.4.

A set $S\subseteq\mathbb{F}^{\leq m}$ is _$\mathcal{A}$ -closed_ if the
following two conditions hold:

  1. (i)

if $(s_{1},\dots,s_{t})\in S$, then $(s_{1},\dots,s_{t-1})\in S$; and

  2. (ii)

if $(s_{1},\ldots,s_{\ell})\in S$, then for all $a_{\ell}\in A_{\ell}$,
$(s_{1},\ldots,s_{\ell-1},a_{\ell})\in S$.

Given a set $X\subseteq\mathbb{F}^{\leq m}$, we refer to the smallest
$\mathcal{A}$-closed set containing $X$ as the _$\mathcal{A}$ -closure_ of
$X$, i.e., $\hat{X}$ is the $\mathcal{A}$-closure of $X$ if $\hat{X}$ is
$\mathcal{A}$-closed, $X\subseteq\hat{X}$, and for all $\mathcal{A}$-closed
$Y\supseteq X$, it holds that $\hat{X}\subseteq Y$.

Globally the $\Sigma\mathrm{RM}$ code can be viewed as a collection of plain
Reed–Muller codes on $1,2,\ldots,m$ variables, related by summation
constraints. The following theorem asserts that this characterisation also
holds locally: over any $\mathcal{A}$-closed subdomain $S$,
$(\Sigma\mathrm{RM}|_{S})^{\perp}$ is spanned by summation constraints
$\\{z_{\vec{s}}\\}_{\vec{s}\in S^{*}}$ and the local constraints on a
collection of Reed-Muller codes. For technical reasons, we show this with
respect to both the “plain” $\Sigma\mathrm{RM}$ code and the subcode
$\mathbf{Z}_{\mathcal{A}}(\Sigma\mathrm{RM})$ of encodings of the zero word.

######  Theorem 6.5.

Let $A_{1},\ldots,A_{m}\subseteq\mathbb{F}$, $\mathcal{A}\ {:=}\
A_{1}\times\cdots\times A_{m}$ and let $S$ be an $\mathcal{A}$-closed set.
Then for $X\in\\{\varnothing,\mathcal{A}\\}$, we have

$(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp}=\operatorname{span}\big{(}\\{z_{\vec{s}}\\}_{\vec{s}\in
S^{*}}\cup\bigcup_{i=1}^{m}(\mathbf{Z}_{X_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{S_{i}})^{\perp}\big{)}$

where $X_{i}\ {:=}\ \\{\vec{x}\in X:\ell(\vec{x})=i\\}$, $S_{i}\ {:=}\
\\{\vec{s}\in S:\ell(\vec{s})=i\\}$, $S^{*}\ {:=}\
\\{(s_{1},\ldots,s_{\ell-1})\in S:\exists s_{\ell}\text{ s.t.
}(s_{1},\ldots,s_{\ell-1},s_{\ell})\in S\\}$, and

$z_{\vec{s}}(\vec{t})\ {:=}\ \begin{cases}1&\text{if $\vec{t}=\vec{s}$;}\\\
-1&\text{if $\vec{t}=(\vec{s},a)$ for some $a\in A_{\ell(\vec{s})+1}$;}\\\
0&\text{ otherwise.}\end{cases}$

We will use the above notation for $X_{i}$, $S_{i}$, $S^{*}$ and
$z_{\vec{s}}(\vec{t})$ throughout the remainder of this section.

We prove Theorem 6.5 by a dimensionality argument. In particular, we show that
any basis for
$(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp}$
which is in echelon form can be mapped to a set of linearly independent
vectors in the span of summation constraints and Reed–Muller constraints.

The key technical tool used here is a “flattening lemma” (Lemma 6.8). This
lemma provides a means to map any constraint $z$ on subcube sums of
$m$-variate polynomials to a new constraint $z^{\prime}$ on subcube sums of
$(m-1)$-variate polynomials, while preserving the value of $\lambda(z)$.
Crucially, in the case where $|\lambda(z)|=m-1$, all dependence of
$z^{\prime}$ on subcube sums vanishes, and we obtain a constraint with respect
to the plain Reed–Muller code.

By repeated applications of the flattening lemma we map any constraint over
subcube sums to a Reed–Muller constraint; we then show by a counting argument
that these “flattened” constraints, along with the summation constraints, span
the dual code.

###### Proof of Theorem 6.5.

Define $Z^{*}\ {:=}\ \\{z_{\vec{s}}\\}_{\vec{s}\in S^{*}}$, and $Z_{i}\ {:=}\
(\mathbf{Z}_{X_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{S_{i}})^{\perp}$
for $i\in[m]$. It follows easily from the definition of $\Sigma\mathrm{RM}$
that
$Z_{1},\ldots,Z_{m}\subseteq(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp}$.
As $S$ is $\mathcal{A}$-closed we also have that
$Z^{*},\subseteq(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp}$.
Hence it suffices to show that
$\dim(\operatorname{span}(Z^{*}\cup\bigcup_{i=1}^{m}Z_{i}))\geq\dim((\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp})$.

Let $\Delta\ {:=}\
\dim((\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp})$.
Fix some ordering $<$ on $S$ so that  (i) $\ell(\vec{s})<\ell(\vec{t})$then
$\vec{s}<\vec{t}$, and  (ii) if $\ell(\vec{s})=\ell(\vec{t})$, $\vec{s}\notin
S^{*}$ and $\vec{t}\in S^{*}$ then $\vec{s}<\vec{t}$.  Let
$b_{1},\ldots,b_{\Delta}$ be a basis for
$(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp}$
which is in echelon form with respect to $<$.

We show that
$\dim(\operatorname{span}(Z^{*}\cup\bigcup_{i=1}^{m}Z_{i}))\geq\Delta$ by
exhibiting a sequence of linearly independent vectors
$b^{\prime}_{1},\ldots,b^{\prime}_{\Delta}\in
Z^{*}\cup\bigcup_{i=1}^{m}Z_{i}$. These vectors are defined as follows:

$b^{\prime}_{i}\ {:=}\ \begin{cases}z_{\vec{\lambda}(b_{i})}&\text{if
$\lambda(b_{i})\in S^{*}$; and}\\\ R(b_{i})&\text{otherwise,}\end{cases}$

where $R$ is as guaranteed by 6.6 below. To show that the $b^{\prime}_{i}$ are
linearly independent, it suffices to show that they are in echelon form with
respect to $<$. This follows since $\lambda(b^{\prime}_{i})=\lambda(b_{i})$
for all $i\in[\Delta]$: if $\lambda(b_{i})\in S^{*}$, then
$\lambda(b^{\prime}_{i})=\lambda(z_{\lambda(b_{i})})=\lambda(b_{i})$; and if
$\lambda(b_{i})\notin S^{*}$ then
$\lambda(b^{\prime}_{i})=\lambda(R(b_{i}))=\lambda(b_{i})$ by 6.6. ∎

It remains to prove the following technical claim.

######  Claim 6.6.

Let $S\subseteq\mathbb{F}^{\leq m}$, $\mathcal{A}\ {:=}\
A_{1}\times\dots\times A_{m}$, $\vec{d}\ {:=}\ (d_{1},\dots,d_{m})$ and
$X\in\\{\varnothing,\mathcal{A}\\}$. If $d_{i}\geq|\mathcal{A}_{i}|-1$ for all
$i\in[m]$, then there is a function
$T\colon(S\to\mathbb{F})\to\bigcup_{i=1}^{m}(S_{i}\to\mathbb{F})$ such that
for all
$z\in(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp}$,
$T(z)\in(\mathbf{Z}_{X_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{S_{i}})^{\perp}$
for $i=|\lambda(z)|$, and if $\lambda(z)\notin S^{*}$,
$\lambda(T(z))=\lambda(z)$.

This claim will be a consequence of Lemma 6.8 (the “flattening lemma”), which
provides a way to transform a constraint on an $m$-variate $\Sigma\mathrm{RM}$
code into a related constraint on an $(m-1)$-variate $\Sigma\mathrm{RM}$ code.

######  Definition 6.7.

Let $S\subseteq\mathbb{F}^{\leq m}$ and $A_{1}\times\dots\times
A_{m}\subseteq\mathbb{F}^{m}$. For $i\in[m]$ and an element $a\in A_{i}$, we
define the “flattening map” $Q_{i,a}\colon(S\to\mathbb{F})\to(S\setminus
S_{i}\to\mathbb{F})$ as follows, for $\vec{s}\in S\setminus S_{i}$:

$Q_{i,a}(z)(\vec{s})\ {:=}\ \begin{cases}z(\vec{s})+\sum_{s_{i}\in
S_{i}}z(\vec{s},s_{i})L_{A_{i},a}(s_{i})&\text{if $\vec{s}\in S_{i-1}\cap
S^{*}$, and}\\\ z(\vec{s})&\text{otherwise.}\end{cases}$

######  Lemma 6.8 (Flattening lemma).

Let $S\subseteq\mathbb{F}^{\leq m}$, $\mathcal{A}\ {:=}\
A_{1}\times\dots\times A_{m}$, $\vec{d}\ {:=}\ (d_{1},\dots,d_{m})$,
$X\in\\{\varnothing,\mathcal{A}\\}$, and let
$z\in(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp}$,
where $d_{m}\geq|A_{m}|-1$. For any point $a_{m}^{*}\in A_{m}$, the function
$Q_{m,a_{m}^{*}}\colon(S\to\mathbb{F})\to(S\setminus S_{m}\to\mathbb{F})$ (see
Definition 6.7) satisfies the following properties:

  1. 1.

If $z$ satisfies $|\lambda(z)|<m-1$, then
$Q_{m,a_{m}^{*}}(z)\in(\mathbf{Z}_{X_{m-1}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A}_{m-1},(d_{1},\dots,d_{m-1})])|_{S\setminus
S_{i}})^{\perp}$ and $\lambda(Q_{m,a_{m}^{*}}(z))=\lambda(z)$.

  2. 2.

If $z$ satisfies $|\lambda(z)|=m-1$, then
$Q_{m,a_{m}^{*}}(z)\in(\mathbf{Z}_{X_{|\lambda(z)|}}(\mathrm{RM}[\mathbb{F},|\lambda(z)|,(d_{1},\ldots,d_{|\lambda(z)|})])|_{S_{|\lambda(z)|}})^{\perp}$,
and furthermore if $\lambda(z)\notin S^{*}$, then
$\lambda(Q_{m,a_{m}^{*}}(z))=\lambda(z)$.

###### Proof.

We will proceed by showing how a constraint on subcube sums of an $m$-variate
polynomials induces a constraint on subcube sums of $(m-1)$-variate
polynomials.

Let
$z\in\left(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S}\right)^{\bot}$.
Define the set $P_{0}\ {:=}\
\\{p\in\mathbb{F}^{\leq\vec{d}}[X_{1},\ldots,X_{m}]:p(\vec{x})=0~{}\forall\vec{x}\in
X\\}$. Then for all polynomials $p\in P_{0}$ it holds that

$\sum_{\vec{s}\in
S}z(\vec{s})\sum_{\vec{a}\in\mathcal{A}_{>\ell(\vec{s})}}p(\vec{s},\vec{a})=0.$
(4)

Let $a_{m}^{*}\in A_{m}$ and define the set of ($m-1$)-variate polynomials
$Q_{0}\ {:=}\
\\{q\in\mathbb{F}^{\leq\vec{d^{\prime}}}[X_{1},\ldots,X_{m-1}]:q(\vec{x})=0~{}\forall\vec{x}\in
X_{m-1}\\}$, where $\vec{d^{\prime}}\ {:=}\ (d_{1},\dots,d_{m-1})$. Then for
any $q\in Q_{0}$, the polynomial defined by $q_{a_{m}^{*}}(x_{1},\dots,x_{m})\
{:=}\ q(x_{1},\dots,x_{m-1})\cdot L_{A_{m},a_{m}^{*}}(x_{m})$ satisfies
$q_{a_{m}^{*}}(\vec{x})=0$ for all $\vec{x}\in X$. So $q_{a_{m}^{*}}\in
P_{0}$. Thus, substituting $q_{a_{m}^{*}}$ into Equation 4 implies that for
all polynomials $q\in Q_{0}$,

$\sum_{\vec{s}\in S\setminus(S_{m-1}\cup
S_{m})}z(\vec{s})\sum_{\vec{a}\in\mathcal{A}^{\prime}_{>\ell(\vec{s})}}q(\vec{s},\vec{a})+\sum_{\vec{s}\in
S_{m-1}}z(\vec{s})q(\vec{s})+\sum_{\vec{s}\in
S_{m-1}}q(\vec{s})\sum_{\begin{subarray}{c}s_{m}\\\ (\vec{s},s_{m})\in
S_{m}\end{subarray}}z(\vec{s},s_{m})L_{\mathcal{A}_{m},a_{m}^{*}}(s_{m})=0,$

where $\mathcal{A}^{\prime}\ {:=}\ \mathcal{A}_{m-1}$. Recall that for points
$(s_{1},\dots,s_{m-1})\notin S^{*}$, there does not exist $s_{m}\in S_{m}$
such that $(s_{1},\dots,s_{m-1},s_{m})\in S$. Thus we can rearrange this
expression as:

$\sum_{\vec{s}\in S\setminus(S_{m-1}\cup
S_{m})}z(\vec{s})\sum_{\vec{a}\in\mathcal{A}^{\prime}_{>\ell(\vec{s})}}q(\vec{s},\vec{a})+\sum_{\vec{s}\in
S_{m-1}\setminus S^{*}}z(\vec{s})q(\vec{s})+\sum_{\vec{s}\in S_{m-1}\cap
S^{*}}q(\vec{s})\left(z(\vec{s})+\sum_{\begin{subarray}{c}s_{m}\\\
(\vec{s},s_{m})\in
S_{m}\end{subarray}}z(\vec{s},s_{m})L_{\mathcal{A}_{m},a_{m}^{*}}(s_{m})\right)=0.$
(5)

Notice that the coefficients of Eq. 5 are precisely the values of
$Q_{m,a_{m}^{*}}$ (Definition 6.7) at each point in $S\setminus S_{m}$. This
demonstrates that for all
$z\in\left(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S}\right)^{\bot}$,
$Q_{m,a_{m}^{*}}(z)\in\left(\mathbf{Z}_{X_{m-1}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A}^{\prime},\vec{d^{\prime}}])|_{S\setminus
S_{m}}\right)^{\bot}$.

Now we will deal with the two cases of the lemma statement separately.

Case (i) $|\lambda(z)|+1<m$. In this case we show that
$\lambda(Q_{m,a_{m}^{*}}(z))=\lambda(z)$.

As $|\lambda(z)|+1<m$, $\lambda(z)\in S\setminus(S_{m}\cup S_{m-1})$. But we
have that $Q_{m,a_{m}^{*}}(z)(\vec{s})=z(\vec{s})$ for all $\vec{s}\in
S\setminus(S_{m}\cup S_{m-1})$, so in particular
$Q_{m,a_{m}^{*}}(z)(\vec{s})=z(\vec{s})=0$ for all $\vec{s}<\lambda(z)$, and
$Q_{m,a_{m}^{*}}(z)(\lambda(z))=z(\lambda(z))\neq 0$. Thus
$\lambda(Q_{m,a_{m}^{*}}(z))=\lambda(z)$.

Case (ii) $|\lambda(z)|+1=m$. First, we show that
$Q_{m,a_{m}^{*}}(z)\in(\mathbf{Z}_{X_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{S_{i}})^{\perp}$,
where $i\ {:=}\ |\lambda(z)|$. Second, we show that if $\lambda(z)\notin
S^{*}$, then $\lambda(Q_{m,a_{m}^{*}}(z))=\lambda(z)$.

For the first part, as $|\lambda(z)|=m-1$, $z(\vec{s})=0$ for all $\vec{s}\in
S\setminus(S_{m-1}\cup S_{m})$. As a result, Equation 5 simplifies greatly and
becomes:

$\sum_{\vec{s}\in S_{|\lambda(z)|}\setminus
S^{*}}z(\vec{s})q(\vec{s})+\sum_{\vec{s}\in S_{|\lambda(z)|}\cap
S^{*}}q(\vec{s})\left(z(\vec{s})+\sum_{\begin{subarray}{c}s_{m}\\\
\vec{s}||s_{m}\in
S_{m}\end{subarray}}z(\vec{s},s_{m})L_{\mathcal{A}_{m},a_{m}^{*}}(s_{m})\right)=0.$
(6)

Note that Equation 6 is a constraint with respect to the Reed-Muller code
$(\mathbf{Z}_{X_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{S_{i}})^{\perp}$.
So
$Q_{m,a_{m}^{*}}(z)\in(\mathbf{Z}_{R_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{S_{i}})^{\perp}$.

For the second part, assume $\lambda(z)\notin S^{*}$. By the definition of
$<$, if $\vec{s}<\lambda(z)$, then it must be that $\vec{s}\notin S^{*}$.
However, if $\vec{s}\notin S^{*}$, then
$Q_{m,a_{m}^{*}}(z)(\vec{s})=z(\vec{s})$. In particular, for
$\vec{s}<\lambda(z)$, $Q_{m,a_{m}^{*}}(z)(\vec{s})=z(\vec{s})=0$, and
$Q_{m,a_{m}^{*}}(z)(\lambda(z))=z(\lambda(z))\neq 0$, so
$\lambda(Q_{m,a_{m}^{*}}(z))=\lambda(z)$. ∎

We now apply Lemma 6.8 to prove 6.6, which will complete the proof of Theorem
6.5.

###### Proof of 6.6.

For each $i\in\\{|\lambda(z)|+1,\dots,m\\}$ arbitrarily chose an element
$a_{i}\in A_{i}$, and for notational convenience, denote by $Q_{i}\ {:=}\
Q_{i,a_{i}}$ the flattening map (Definition 6.7). For each
$z\in(\mathbf{Z}_{X}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{S})^{\perp}$,
define the value of $T(z)\ {:=}\ (Q_{|\lambda(z)|+1}\circ\dots\circ
Q_{m-1}\circ Q_{m})(z)$.

By part 1 of Lemma 6.8, we see that $(Q_{|\lambda(z)|+2}\circ\dots\circ
Q_{m})(z)\in(\mathbf{Z}_{X_{i+1}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A}_{i+1},(d_{1},\dots,d_{i+1})])|_{S\setminus
S_{m}})^{\perp}$, with $\lambda((Q_{|\lambda(z)|+2}\circ\dots\circ
Q_{m})(z))=\lambda(z)$. Combining this with part 2 of Lemma 6.8 we see that
$T(z)\ {:=}\ (Q_{|\lambda(z)|+1}\circ\dots\circ
Q_{m})(z)\in(\mathbf{Z}_{X_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{S_{i}})^{\perp}$,
and provided that $\lambda(z)\notin S^{*}$, then $\lambda(T(z))=\lambda(z).$ ∎

###  6.2 An $\ell$-constraint locator for $\Sigma$RM

In this section we construct an constraint locator for $\Sigma\mathrm{RM}$, by
combining the structure implied by Theorem 6.5 with the constraint locator we
constructed in Section 5. We will often denote $\Sigma\mathrm{RM}\ {:=}\
\Sigma\mathrm{RM}[\mathbb{F},m,\vec{d}]$ when $\mathbb{F},m,\vec{d}$ are clear
from context.

######  Construction 6.9.

An $\ell$-constraint locator for
$\mathsf{ENC}_{\Sigma\mathrm{RM}(\vec{d},\mathcal{A})}$. For each $i\in[m]$,
let $\mathsf{CL}_{i}$ be an $\ell_{i}$-constraint locator for
$\mathsf{ENC}_{\mathrm{RM}((d_{1},\dots,d_{i}),\mathcal{A}_{i})}$ (cf. Theorem
5.2). Input: a subdomain $I\subseteq\mathbb{F}^{m}.$
$\mathsf{CL}_{\Sigma}(I)$: 1. Compute the $\mathcal{A}$-closure $\hat{I}$ of
$I$. 2. For each $i\in[m]$, compute $(R_{i},Z_{i})\ {:=}\
\mathsf{CL}_{i}(\hat{I}_{i})$, where $\hat{I}_{i}\ {:=}\
\\{\vec{x}\in\hat{I}\colon\ell(\vec{x})=i\\}$. 3. Define the set $R\ {:=}\
\bigcup_{i=1}^{m}R_{i}$ and compute the $\mathcal{A}$-closure $\hat{R}$ of
$R$. 4. For each $i\in[m]$, define $Z_{i}^{\prime}$ to be the natural
embedding of $Z_{i}$ into the space of matrices
$\mathbb{F}^{k_{i}\times\hat{R}_{i}\sqcup\hat{I}}$ (by appropriate padding
with $|\hat{R}_{i}|-|R_{i}|$ columns of zeros), where $k_{i}$ is the number of
rows of $Z_{i}$. 5. Construct the matrix $Z^{\prime}\ {:=}\
\left(\begin{array}[]{cccc}Z_{1}^{\prime}&\mathbf{0}&\dots&\mathbf{0}\\\
\mathbf{0}&Z_{2}^{\prime}&\dots&\mathbf{0}\\\ \vdots&\vdots&\ddots&\vdots\\\
\mathbf{0}&\mathbf{0}&\dots&Z_{m}^{\prime}\\\ \end{array}\right)\enspace.$ 6.
Construct the matrix $Z^{*}$ whose $(\vec{s},\vec{\gamma})$-th entry, for
$\vec{s}\in(\hat{R}\sqcup\hat{I})^{*}$, and
$\vec{\gamma}\in\hat{R}\sqcup\hat{I}$, is defined by
$z_{\vec{s}}(\vec{\gamma})=\begin{cases}1&\text{if}~{}\vec{\gamma}=\vec{s},\\\
-1&\text{if}~{}\vec{\gamma}=(\vec{s},a)~{}\text{for some}~{}a\in
A_{\ell(\vec{\gamma})+1},\\\ 0&\text{otherwise.}\end{cases}$ 7. Define $Z$ to
be the matrix obtained by vertically stacking $Z^{\prime}$ on top of $Z^{*}$.
8. Compute a basis $B$ for the space
$\\{(\vec{r},\vec{\beta})\in\mathbb{F}^{\hat{R}}\times\mathbb{F}^{I}:\exists\vec{\gamma}\in\mathbb{F}^{\hat{I}\setminus
I},Z(\vec{r},\vec{\beta},\vec{\alpha})^{T}=0\\}$. 9. Output $(\hat{R},B)$.

Our proof of correctness for 6.9 consists of two main steps. The first is
showing that $\ker(B)=\Sigma\mathrm{RM}|_{\hat{R}\sqcup I}$, which we
accomplish by appealing to Theorem 6.5. We then show that
$(\vec{r},\vec{\beta})\in\Sigma\mathrm{RM}|_{\hat{R}\sqcup I}$ if and only if
for all messages $m\in\mathcal{M}$ such that $m|_{\hat{R}}=\vec{r}$, we have
$(m,\vec{\beta})\in\Sigma\mathrm{RM}|_{\bar{\mathcal{A}}\sqcup I}$.

######  Claim 6.10.

Let $I\subseteq\mathbb{F}^{m}$ and let $(\hat{R},B)\ {:=}\
\mathsf{CL}_{\Sigma}(I)$ (cf. 6.9), then
$\ker(B)=\Sigma\mathrm{RM}[\mathbb{F},m,\vec{d}]|_{\hat{R}\sqcup I}$.

###### Proof.

It suffices to show that $\ker(Z)=\Sigma\mathrm{RM}|_{\hat{R}\sqcup\hat{I}}$
(for $Z$ as in 6.9). This is because $(\vec{r},\vec{\beta})\in\ker(B)$ if and
only if there exists $\vec{\gamma}\in\mathbb{F}^{\hat{I}\setminus I}$ such
that $(\vec{r},\vec{\beta},\vec{\gamma})\in\ker(Z)$. So
$\ker(B)=\ker(Z)|_{\hat{R}\sqcup I}.$ If
$\ker(Z)=\Sigma\mathrm{RM}|_{\hat{R}\sqcup\hat{I}}$, then upon restricting
both sides of the equivalence to $\hat{R}\sqcup I$, we have that
$\ker(B)=\Sigma\mathrm{RM}|_{\hat{R}\sqcup I}$, as required.

To see that $\ker(Z)=\Sigma\mathrm{RM}|_{\hat{R}\sqcup\hat{I}}$, consider the
following. By construction, the rows of $Z$ consist of trivial constraints
over $(\hat{I}\sqcup\hat{R})^{*}$ and Reed-Muller constraints on the set
$R_{i}\sqcup\hat{I}$ padded with zeros so as to be supported on
$\hat{R}\sqcup\hat{I}$. That is,

$\mathsf{rowspace}(Z)=\operatorname{span}\big{(}\\{z_{\vec{s}}\\}_{\vec{s}\in(\hat{R}\sqcup\hat{I})^{*}}\cup\bigcup_{i=1}^{m}({\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})]}|_{{R_{i}\sqcup\hat{I}}_{i}})^{\perp}\times\\{0\\}^{\hat{R}_{i}\setminus
R_{i}}\big{)}.$

By the correctness of each $\mathsf{CL}_{i}$, we know that for all $i\in[m]$,
for all constraints
$z\in(\mathrm{RM}[\mathbb{F},i,(d_{1},\dots,d_{i})]|_{\mathcal{A}_{i}\sqcup\hat{I}})^{\perp}$,
$z(\vec{\alpha})=0$ for all $\vec{\alpha}\in\mathcal{A}_{i}\setminus R_{i}$.
Therefore as $R_{i}\subseteq\hat{R}_{i}\subseteq\mathcal{A}_{i}$, we have that
$(\mathrm{RM}[\mathbb{F},i,(d_{1},\dots,d_{i})]|_{\hat{R}_{i}\sqcup\hat{I}})^{\perp}=(\mathrm{RM}[\mathbb{F},i,(d_{1},\dots,d_{i})]|_{R_{i}\sqcup\hat{I}})^{\perp}\times\\{0\\}^{\hat{R}_{i}\setminus
R_{i}}$. Hence,

$\mathsf{rowspace}(Z)=\operatorname{span}\big{(}\\{z_{\vec{s}}\\}_{\vec{s}\in(\hat{R}\sqcup\hat{I})^{*}}\cup\bigcup_{i=1}^{m}({\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})]}|_{{\hat{R}_{i}\sqcup\hat{I}}_{i}})^{\perp}\big{)}=(\Sigma\mathrm{RM}|_{\hat{R}\sqcup\hat{I}})^{\perp},$

where the final equality follows from Theorem 6.5 and the fact that
$\hat{R}\sqcup\hat{I}$ is $\mathcal{A}$-closed. In particular, we have shown
that $Z$ is a parity check matrix for
$\Sigma\mathrm{RM}|_{\hat{R}\sqcup\hat{I}}$. In other words,
$\ker(Z)=\Sigma\mathrm{RM}|_{\hat{R}\sqcup\hat{I}}$. ∎

Now we focus on the second part of our proof of correctness: showing that
$(\vec{r},\vec{\beta})\in\Sigma\mathrm{RM}|_{\hat{R}\sqcup I}$ if and only if
for all messages $m\in\mathcal{M}$ such that $m|_{\hat{R}}=\vec{r}$, we have
$(m,\vec{\beta})\in\Sigma\mathrm{RM}|_{\bar{\mathcal{A}}\sqcup I}$. We
accomplish this via the following property of linear codes, whose proof is
deferred to Section A.5.

######  Claim 6.11.

Let $C\subseteq\mathbb{F}^{D}$ be a linear code, and let $U\subseteq
V\subseteq D$, $I\subseteq D$ be such that
$\mathbf{Z}_{U}(C)|_{I}=\mathbf{Z}_{V}(C)|_{I}$. Then $(u,x)\in C|_{U\sqcup
I}$ if and only if for all $v\in C|_{V}$ such that $v|_{U}=u$, $(v,x)\in
C|_{V\sqcup I}$.

We prove that
$\mathbf{Z}_{\mathcal{A}}(\Sigma\mathrm{RM})|_{\hat{I}}=\mathbf{Z}_{\hat{R}}(\Sigma\mathrm{RM})|_{\hat{I}}$
where $\hat{I},\hat{R}$ are as above. To do this, we first show an analogous
statement for “plain” $\mathrm{RM}$, and then lift that result to
$\Sigma\mathrm{RM}$ via Theorem 6.5.

######  Claim 6.12.

Let $\mathcal{A}=A_{1}\times\dots\times A_{m}\subseteq\mathbb{F}^{m}$ and let
$S\subseteq\mathbb{F}^{m}$. It holds that
$\mathbf{Z}_{\mathcal{A}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{S}=\mathbf{Z}_{R}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{S}$,
where $(R,Z)\ {:=}\ \mathsf{CL}(S)$, for an $\ell$-constraint locator
$\mathsf{CL}$ for $\mathsf{ENC}_{\mathrm{RM}(\vec{d},\mathcal{A})}$.

###### Proof.

As $R\subseteq\mathcal{A}$, it is clear that
$\mathbf{Z}_{\mathcal{A}}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{S}\subseteq\mathbf{Z}_{R}(\mathrm{RM}[\mathbb{F},m,\vec{d}])|_{S}$.
We now argue the reverse containment. For brevity we write $\mathrm{RM}$ for
$\mathrm{RM}[\mathbb{F},m,\vec{d}]$.

Let $w\in\mathrm{RM}$ such that $w(r)=0$ for all $r\in R$. Then $w|_{S}$ is a
general element of $\mathbf{Z}_{R}(\mathrm{RM})|_{S}$. We will show that there
exists $w^{\prime}\in\mathrm{RM}$ which agrees with $w$ on $S$, but is zero on
$\mathcal{A}$, i.e., $w^{\prime}|_{S}=w|_{S}$ and
$w^{\prime}|_{\mathcal{A}}=\vec{0}$.

By the correctness of $\mathsf{CL}$, all constraints on $\mathcal{A}\sqcup S$
with respect to $\mathrm{RM}$ are supported only on $R\sqcup S$; in
particular, they have no support on the set $\mathcal{A}\setminus R$. For
$\alpha\in\mathcal{A}\setminus R$, define $w_{\alpha}\colon\mathcal{A}\sqcup
S\to\mathbb{F}$ by $w_{\alpha}(\alpha)\ {:=}\ 1$ and $w_{\alpha}(\beta)\ {:=}\
0$ for all $\beta\in\mathcal{A}\sqcup S\setminus\\{\alpha\\}$. Then since
$w_{\alpha}$ is only nonzero in $\mathcal{A}\setminus R$,
$w_{\alpha}\in\mathrm{RM}|_{\mathcal{A}\sqcup S}$, and so
$w_{\alpha}=w_{\alpha}^{\prime}|_{\mathcal{A}\sqcup S}$ for
$w_{\alpha}^{\prime}\in\mathrm{RM}$. Consider the codeword defined by

$w^{\prime}\ {:=}\ w-\sum_{\alpha\in\mathcal{A}\setminus
R}w(\alpha)w_{\alpha}^{\prime}.$

This choice of $w^{\prime}$ satisfies
$w^{\prime}\in\mathbf{Z}_{\mathcal{A}}(\mathrm{RM})$, and
$w^{\prime}|_{S}=w|_{S}$. Thus
$w|_{S}\in\mathbf{Z}_{\mathcal{A}}(\mathrm{RM})|_{S}$. ∎

######  Corollary 6.13.

For $\hat{I},R$ as in 6.9,
$(\mathbf{Z}_{\mathcal{A}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{\hat{I}})^{\perp}=(\mathbf{Z}_{\hat{R}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{\hat{I}})^{\perp}$.

###### Proof.

It is clear that
$(\mathbf{Z}_{\hat{R}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{\hat{I}})^{\perp}\subseteq(\mathbf{Z}_{\mathcal{A}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{\hat{I}})^{\perp}$,
so we show the reverse inclusion.

For $R_{i},Z_{i},\hat{I}_{i}$ as in 6.9, we have that

$\displaystyle(\mathbf{Z}_{\mathcal{A}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d})|_{\hat{I}})^{\perp}$
$\displaystyle=\operatorname{span}\big{(}\\{z_{\vec{s}}\\}_{\vec{s}\in{\hat{I}}^{*}}\cup\bigcup_{i=1}^{m}(\mathbf{Z}_{\mathcal{A}_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{\hat{I}_{i}})^{\perp}\big{)}$
$\displaystyle=\operatorname{span}\big{(}\\{z_{\vec{s}}\\}_{\vec{s}\in\hat{I}^{*}}\cup\bigcup_{i=1}^{m}(\mathbf{Z}_{R_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{\hat{I}_{i}})^{\perp}\big{)}$
$\displaystyle\subseteq\operatorname{span}\big{(}\\{z_{\vec{s}}\\}_{\vec{s}\in\hat{I}^{*}}\cup\bigcup_{i=1}^{m}(\mathbf{Z}_{{\hat{R}}_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{\hat{I}_{i}})^{\perp}\big{)}$
$\displaystyle\subseteq(\mathbf{Z}_{\hat{R}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{\hat{I}})^{\perp}.$

The first equality is a consequence of Theorem 6.5. The second equality is a
consequence of 6.12. The penultimate inclusion is true as
$R_{i}\subseteq\hat{R}_{i}$ for each $i\in[m]$. The final inclusion follows
from the fact that trivially
$(\mathbf{Z}_{\hat{R}_{i}}(\mathrm{RM}[\mathbb{F},i,(d_{1},\ldots,d_{i})])|_{\hat{I}_{i}})^{\perp}\subseteq(\mathbf{Z}_{\hat{R}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{\hat{I}})^{\perp}$
for each $i\in[m]$ and as $\hat{R}$ is $\mathcal{A}$-closed, we also have that
$\\{z_{\vec{s}}\\}_{\vec{s}\in\hat{I}^{*}}\subseteq(\mathbf{Z}_{\hat{R}}(\Sigma\mathrm{RM}[\mathbb{F},\mathcal{A},\vec{d}])|_{\hat{I}})^{\perp}$.
∎

###### Proof of Theorem 6.2.

Correctness. By 6.10, we have that $\ker(B)=\Sigma\mathrm{RM}|_{\hat{R}\sqcup
I}$. Then by 6.11, setting $U\ {:=}\ \hat{R}$ and $V\ {:=}\
\bar{\mathcal{A}}$, and Corollary 6.13, noting that
$\mathsf{ENC}_{\Sigma\mathrm{RM}(\vec{d},\mathcal{A})}$ is a systematic
encoding (that is $\mathcal{M}=\Sigma\mathrm{RM}|_{\bar{\mathcal{A}}}$), it
follows that
$(\vec{r},\vec{\beta})\in\Sigma\mathrm{RM}|_{\hat{R}\sqcup\hat{I}}$ if and
only if for all messages $m\in\mathcal{M}$ such that $m|_{\hat{R}}=\vec{r}$,
we have
$(m,\vec{\beta})\in\Sigma\mathrm{RM}|_{\bar{\mathcal{A}}\sqcup\hat{I}}$. Thus,
taking the restriction of both sides,
$(\vec{r},\vec{\beta}|_{I})\in\Sigma\mathrm{RM}|_{\hat{R}\sqcup I}$ if and
only if for all messages $m\in\mathcal{M}$ such that $m|_{\hat{R}}=\vec{r}$,
we have $(m,\vec{\beta}|_{I})\in\Sigma\mathrm{RM}|_{\bar{\mathcal{A}}\sqcup
I}$. This is sufficient since, by definition of the encoding,
$\vec{\beta}\in\mathsf{supp}(\mathsf{ENC}_{\Sigma\mathrm{RM}(\vec{d},\mathcal{A})}(m)|_{I})$
if and only if $(m,\vec{\beta})\in\Sigma\mathrm{RM}|_{\bar{\mathcal{A}}\sqcup
I}$.

Efficiency. By 6.14 (below), $|\hat{R}|\leq(\sum_{i=1}^{m}|A_{i}|+m+1)|R|$ and
$|\hat{I}|\leq(\sum_{i=1}^{m}|A_{i}|+m+1)|I|$. By Theorem 5.4,
$|R_{i}|\leq|\hat{I}|\leq(\sum_{i=1}^{m}|A_{i}|+m+1)|I|$. As
$|R|\leq\sum_{i=1}^{m}|R_{i}|\leq m(\sum_{i=1}^{m}|A_{i}|+m+1)|I|$, we have
$|\hat{R}|\leq m(\sum_{i=1}^{m}|A_{i}|+m+1)^{2}|I|$.

The runtime follows from 6.14 and Theorem 5.2, as $\mathsf{CL}_{i}$ runs in
time $\mathrm{poly}(\log|\mathbb{F}|,m,\max_{i}d_{i},n)$. ∎

######  Claim 6.14.

Let $I\subseteq\mathbb{F}^{\leq m}$ and $\mathcal{A}=A_{1}\times\dots\times
A_{m}$. Then there exists a set $\hat{I}\subseteq\mathbb{F}^{\leq m}$ such
that $I\subseteq\hat{I}$ and $\hat{I}$ is $\mathcal{A}$-closed, satisfying
$|\hat{I}|\leq(\sum_{i=1}^{m}|A_{i}|+m+1)|I|$. Moreover, $\hat{I}$ can be
computed in time $\mathrm{poly}(m,|I|,|A_{1}|,\dots,|A_{m}|)$.

###### Proof.

We construct $\hat{I}$ as follows. Let $I_{i}\ {:=}\ \\{x\in I:|x|=i\\}$.
Initialise $\hat{I}\ {:=}\ I$. For each $(x_{1},\dots,x_{m})\in I_{m}$, we add
the point $(x_{1},\dots,x_{m-1})$ and for each $a_{m}\in A_{m}$ we add the
point $(x_{1},\dots,x_{m-1},a_{m})$ to $\hat{I}$. Then repeat this process for
$I_{m-1},I_{m-2},\dots,I_{1}$. By construction, $\hat{I}$ is
$\mathcal{A}$-closed.

Now we argue about the size of $\hat{I}$. Note that for each point in $I$ at
most $\sum_{i=1}^{m}|A_{i}|+m$ points are added to $\hat{I}$. Thus it holds
that $|\hat{I}|\leq(\sum_{i=1}^{m}|A_{i}|+m+1)|I|$. The efficiency follows
from this bound. ∎

##  7 Constraint location for $\Sigma$AntiSym

In this section we define the code $\mathrm{AntiSym}$ of antisymmetric
functions, and provide a constraint locator for an encoding function related
to its sum code $\Sigma\mathrm{AntiSym}$.

######  Definition 7.1.

Let $\mathcal{A}\ {:=}\ A_{1}\times\cdots\times A_{m}$ be such that
$A_{i}=A_{m-i+1}$ for all $1\leq i\leq m$. We define

$\mathrm{AntiSym}[\mathcal{A}]\ {:=}\
\\{w\in\mathbb{F}^{\mathcal{A}}:\forall\vec{x}\in\mathcal{A},w(\vec{x})+w(\vec{x}_{\mathsf{rev}})=0\\}~{}.$

The code $\Sigma\mathrm{AntiSym}$ is the sum code of $\mathrm{AntiSym}$ (see
Definition 3.6).

The main theorem of this section is the following, which gives an efficient
constraint locator for $\Sigma\mathrm{AntiSym}$ with polynomial locality.

######  Theorem 7.2.

Let $\mathcal{A}$ be as above. Let $\mathcal{M}\ {:=}\
\\{F\colon\mathcal{A}\cup\\{\bot\\}\to\mathbb{F}\mid
F(\bot)=\sum_{\vec{a}\in\mathcal{A}}F(\vec{a})\\}$. Let
$\mathsf{ENC}_{\Sigma\mathrm{AntiSym}}\colon\mathcal{M}\to\mathbb{F}^{\bar{\mathcal{A}}}$
be the following randomised encoding:

$\mathsf{ENC}_{\Sigma\mathrm{AntiSym}}(F)\ {:=}\ \Sigma[F|_{\mathcal{A}}+G],$

where $G$ is a codeword sampled uniformly at random from
$\mathrm{AntiSym}[\mathcal{A}]$.

$\mathsf{ENC}_{\Sigma\mathrm{AntiSym}}$ has an $\ell$-constraint locator for
$\ell(n)=n^{2}m^{2}+1+O(n^{4}m^{4}/|\mathcal{A}|)$, running in time
$\mathrm{poly}(a,m,n)$, where $a\ {:=}\ \sum_{i}|A_{i}|$.

In Section 7.1 we analyse the combinatorial structure of
$\Sigma\mathrm{AntiSym}|_{I}^{\perp}$, obtaining a bound on the “complexity”
of constraints in terms of the size of $I$. In Section 7.2, we show how this
bound leads to an efficient constraint locator for
$\mathsf{ENC}_{\Sigma\mathrm{AntiSym}}$.

###  7.1 Properties of $\Sigma\mathrm{AntiSym}$

We start by introducing some useful notation.

######  Definition 7.3.

We say $\vec{a}\in\bar{\mathcal{A}}$ is a _prefix_ of
$\vec{b}\in\bar{\mathcal{A}}$ if $\ell(\vec{a})\leq\ell(\vec{b})$ and
$(a_{1},\ldots,a_{\ell(\vec{a})})=(b_{1},\ldots,b_{\ell(\vec{a})})$. A subset
$J\subseteq\bar{\mathcal{A}}$ is _prefix-free_ if for all $\vec{a},\vec{b}\in
J$, if $\vec{a}$ is a prefix of $\vec{b}$ then $\vec{a}=\vec{b}$.

We associate with an element $\vec{a}\in\bar{\mathcal{A}}$ the set
$\vec{a}\times\mathcal{A}_{>\ell(\vec{a})}$; we denote this set also by
$\vec{a}$. In particular,
$|\vec{a}|=|\mathcal{A}_{>\ell(\vec{a})}|=\prod_{i=\ell(\vec{a})+1}^{m}|A_{i}|$.
(See Definition 3.6.)

It is straightforward to see that $\vec{b}\subseteq\vec{a}$ if and only if
$\vec{a}$ is a prefix of $\vec{b}$. The following simple proposition gives a
useful alternative characterisation of $\mathrm{AntiSym}$.

######  Proposition 7.4.

$w\in\mathrm{AntiSym}[\mathcal{A}]$ if and only if there exists
$f\in\mathbb{F}^{\mathcal{A}}$ such that
$w(\vec{x})=f(\vec{x})-f(\vec{x}_{\mathsf{rev}})$.

###### Proof.

For the “if” direction, note that
$w(\vec{x})+w(\vec{x}_{\mathsf{rev}})=f(\vec{x})-f(\vec{x}_{\mathsf{rev}})+f(\vec{x}_{\mathsf{rev}})-f(\vec{x})=0$
for all $\vec{x}\in\mathcal{A}$. For the “only if” direction, let
$w\in\mathrm{AntiSym}[\vec{A}]$, and consider some strict total ordering $<$
on $\mathcal{A}$. Define

$f(\vec{x})\ {:=}\ \begin{cases}w(\vec{x})&\text{if
$\vec{x}<\vec{x}_{\mathsf{rev}}$, and}\\\ 0&\text{otherwise.}\end{cases}$

Then for all $\vec{x}$,

$f(\vec{x})-f(\vec{x}_{\mathsf{rev}})=\begin{cases}w(\vec{x})&\text{ if
$\vec{x}<\vec{x}_{\mathsf{rev}}$, and}\\\ -w(\vec{x}_{\mathsf{rev}})&\text{ if
$\vec{x}_{\mathsf{rev}}<\vec{x}$}\end{cases}=w(\vec{x})~{}.\qed$

######  Definition 7.5.

For $\vec{a}=(a_{1},\ldots,a_{\ell})\in\bar{\mathcal{A}}$, we define the
_reverse set_ $\vec{a}_{\mathsf{rev}}\ {:=}\
\bar{\mathcal{A}}_{m-\ell}\times(a_{\ell},\ldots,a_{1})$. For a set
$H\subseteq\bar{\mathcal{A}}$, we define $H_{\mathsf{rev}}\ {:=}\
\\{\vec{a}_{\mathsf{rev}}:\vec{a}\in H\\}$.

We say that $H$ is _symmetric_ if $\cup H=\cup H_{\mathsf{rev}}$, where $\cup
H\ {:=}\ \cup_{\vec{h}\in H}\vec{h}$. We say that $H$ is _minimal symmetric_
if $H$ is symmetric and for all nonempty $H^{\prime}\subsetneq H$,
$H^{\prime}$ is not symmetric.

######  Proposition 7.6.

If $H\subseteq\bar{\mathcal{A}}$ is symmetric and prefix-free, then
$H=\cup_{i=1}^{k}H_{i}$ for $H_{1},\ldots,H_{k}\subseteq H$ where each $H_{i}$
is minimal symmetric and $H_{i}\cap H_{j}=\varnothing$ for $i\neq j$.

###### Proof.

We proceed by induction on the size of $H$. Indeed, suppose that the statement
is true for all sets $H^{\prime}\subseteq\bar{\mathcal{A}}$ of size less than
$n$, and let $H\subseteq\bar{\mathcal{A}}$ be a set of size $n$. If $H$ is
minimal symmetric, then the statement holds trivially, so suppose not. Then
there is a nonempty symmetric $H^{\prime}\subsetneq H$. Since $H$ is prefix-
free, $\cup(H\setminus H^{\prime})=(\cup H)\setminus(\cup H^{\prime})=(\cup
H_{\mathsf{rev}})\setminus(\cup H^{\prime}_{\mathsf{rev}})=\cup(H\setminus
H^{\prime})_{\mathsf{rev}}$; hence $H\setminus H^{\prime}$ is also symmetric.
Since $H^{\prime}$ and $H\setminus H^{\prime}$ are strictly smaller than $H$,
we can apply the inductive hypothesis to complete the proof. ∎

The following lemma shows that, for $G$ prefix-free,
$\Sigma\mathrm{AntiSym}|_{G}^{\perp}$ has a basis of constraints of the form
“$\sum_{\vec{h}\in H}w(\vec{h})=0$”, taken over all minimal symmetric subsets
$H\subseteq G$.

######  Lemma 7.7.

Let $G\subseteq\bar{\mathcal{A}}$ be prefix-free. For $H\subseteq G$, let
$1_{H}\colon G\to\mathbb{F}$ be the indicator vector for $H$, i.e.,
$1_{H}(\vec{h})=1$ if $\vec{h}\in H$ and $0$ otherwise. A basis for
$\Sigma\mathrm{AntiSym}[\mathcal{A}]|_{G}^{\perp}$ is
$\\{1_{H}\\}_{H\in\mathcal{H}}$ where $\mathcal{H}$ is the set of all minimal
symmetric subsets of $G$.

###### Proof.

Let $B\ {:=}\ \\{1_{H}\\}_{H\in\mathcal{H}}$. First, note that Proposition 7.6
implies that for all $H\neq H^{\prime}\in\mathcal{H}$, $H\cap
H^{\prime}=\varnothing$. Hence $B$ is a linearly independent set. It is also
straightforward to see that
$B\subseteq\Sigma\mathrm{AntiSym}[\mathcal{A}]|_{G}^{\perp}$. It remains to
show that
$\operatorname{span}(B)=\Sigma\mathrm{AntiSym}[\mathcal{A}]|_{G}^{\perp}$.

Suppose that $z\in\Sigma\mathrm{AntiSym}[\mathcal{A}]|_{G}^{\perp}$;
equivalently, by Proposition 7.4, for all $f\colon\mathcal{A}\to\mathbb{F}$,

$\sum_{\vec{a}\in
G}z(\vec{a})\sum_{\vec{x}\in\vec{a}}f(\vec{x})=\sum_{\vec{a}\in
G}z(\vec{a})\sum_{\vec{x}\in\vec{a}}f(\vec{x}_{\mathsf{rev}})~{}.$

Let $S_{\gamma}\ {:=}\ \\{\vec{a}\in G:z(\vec{a})=\gamma\\}$. Then we can
write

$\sum_{\gamma\in\mathbb{F}}\gamma\sum_{\vec{a}\in
S_{\gamma}}\sum_{\vec{x}\in\vec{a}}f(\vec{x})=\sum_{\gamma\in\mathbb{F}}\gamma\sum_{\vec{a}\in
S_{\gamma}}\sum_{\vec{x}\in\vec{a}}f(\vec{x}_{\mathsf{rev}})~{}.$

Fix $\gamma^{*}\in\mathbb{F}$, $\vec{a}^{*}\in S_{\gamma^{*}}$, and let
$\vec{x}^{*}\in\vec{a}^{*}$. Let $f=1_{\vec{x}^{*}}$ be the indicator function
for $\vec{x}^{*}$. It follows that

$\gamma^{*}=\sum_{\gamma\in\mathbb{F}}\gamma\sum_{\vec{a}\in
S_{\gamma}}\sum_{\vec{x}\in\vec{a}}1_{\vec{x}^{*}}(\vec{x}_{\mathsf{rev}})=\gamma^{\prime}$

where $\gamma^{\prime}\in\mathbb{F}$ is unique such that
$\vec{x}_{\mathsf{rev}}^{*}\in\cup S_{\gamma^{\prime}}$. Thus
$\vec{x}_{\mathsf{rev}}^{*}\in\cup S_{\gamma^{*}}$; equivalently,
$\vec{x}^{*}\in\cup(S_{\gamma^{*}})_{\mathsf{rev}}$. It follows that for all
$\gamma$, $\cup S_{\gamma}\subseteq\cup(S_{\gamma})_{\mathsf{rev}}$; a similar
argument establishes that in fact $S_{\gamma}$ is symmetric. By Proposition
7.6, $S_{\gamma}$ is a union of minimal symmetric sets. It follows that
$z\in\operatorname{span}(B)$. ∎

Next, we prove the main technical lemma of this section.

######  Lemma 7.8.

Let $H,G\subseteq\bar{\mathcal{A}}$ be prefix-free with
$|H|\cdot|G|\leq|\mathcal{A}|/4$. Suppose that $\cup H=\cup G_{\mathsf{rev}}$.
Then

$|\cup H|\geq\frac{K}{2}(1+\sqrt{1-4|H|\cdot|G|/K})\qquad\text{or}\qquad|\cup
H|\leq\frac{K}{2}(1-\sqrt{1-4|H|\cdot|G|/K})~{}.$

In particular,

$\min(|\cup H|,|\mathcal{A}|-|\cup
H|)\leq|H|\cdot|G|+O(|H|^{2}|G|^{2}/|\mathcal{A}|)~{}.$

Taking $G=H$, we obtain strong bounds on the support size of symmetric sets:
if $H$ is symmetric then $\cup H$ must be of size either $\mathrm{poly}(|H|)$
or $|\mathcal{A}|-\mathrm{poly}(|H|)$.

######  Corollary 7.9.

If $H\subseteq\bar{\mathcal{A}}$ is symmetric and prefix-free, then

$\min(|\cup H|,|\mathcal{A}|-|\cup
H|)\leq|H|^{2}+O(|H|^{4}/|\mathcal{A}|)~{}.$

Before proving Lemma 7.8, we state and prove a simple but crucial claim about
the size of the intersection of sets $\vec{a}$ and $\vec{b}_{\mathsf{rev}}$
for general $\vec{a},\vec{b}\in\bar{\mathcal{A}}$.

######  Claim 7.10.

For any $\vec{a},\vec{b}\in\bar{\mathcal{A}}$,

$|\vec{a}\cap\vec{b}_{\mathsf{rev}}|\leq\begin{cases}\prod_{j=\ell(\vec{a})+1}^{m-\ell(\vec{b})}|A_{j}|&\text{if
$\ell(\vec{a})+\ell(\vec{b})<m$}\\\ 1&\text{otherwise.}\end{cases}$

###### Proof.

Recall that, if $\ell(\vec{a})+\ell(\vec{b})<m$,

$\displaystyle\vec{a}$
$\displaystyle=\\{a_{1}\\}\times\cdots\times\\{a_{\ell(\vec{a})}\\}\times
A_{\ell(\vec{a})+1}\times\cdots\times A_{m-\ell(\vec{b})}\times\cdots\times
A_{m}$ $\displaystyle\vec{b}_{\mathsf{rev}}$
$\displaystyle=A_{1}\times\cdots\times A_{\ell(\vec{a})}\times\cdots\times