# Approximate Polymorphisms

Gilad Chase Yuval Filmus Dor Minzer Elchanan Mossel Nitin Saurabh The Henry
and Marylin Taub Faculty of Computer Science, Technion, Israel.The Henry and
Marylin Taub Faculty of Computer Science, Technion, Israel. This project has
received funding from the European Union’s Horizon 2020 research and
innovation programme under grant agreement No 802020-ERC-HARMONIC.Department
of Mathematics, Massachusetts Institute of Technology, Cambridge,
USA.Department of Mathematics and IDSS, Massachusetts Institute of Technology,
Cambridge, USA.Department of Computer Science, Technion, Israel. This project
has received funding from the European Union’s Horizon 2020 research and
innovation programme under grant agreement No 802020-ERC-HARMONIC.

###### Abstract

For a function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$, a function
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is called a $g$-polymorphism if their
actions commute:
$f(g(\mathsf{row}_{1}(Z)),\ldots,g(\mathsf{row}_{n}(Z)))=g(f(\mathsf{col}_{1}(Z)),\ldots,f(\mathsf{col}_{m}(Z)))$
for all $Z\in\\{0,1\\}^{n\times m}$. The function $f$ is called an approximate
$g$-polymorphism if this equality holds with probability close to $1$, when
$Z$ is sampled uniformly. A pair of functions
$f_{0},f_{1}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ are called a skew
$g$-polymorphism if
$f_{0}(g(\mathsf{row}_{1}(Z)),\ldots,g(\mathsf{row}_{n}(Z)))=g(f_{1}(\mathsf{col}_{1}(Z)),\ldots,f_{1}(\mathsf{col}_{m}(Z)))$
for all $Z\in\\{0,1\\}^{n\times m}$.

We study the structure of exact polymorphisms as well as approximate
polymorphisms. Our results include:

  1. 1.

We prove that an approximate polymorphism $f$ must be close to an exact _skew_
polymorphism;

  2. 2.

We give a characterization of exact skew polymorphisms, showing that besides
trivial cases, only the functions
$g=\mathsf{AND},\mathsf{XOR},\mathsf{OR},\mathsf{NAND},\mathsf{NOR},\mathsf{NXOR}$
admit non-trivial exact skew polymorphisms.

We also study the approximate polymorphism problem in the list-decoding regime
(i.e., when the probability equality holds is not close to $1$, but is bounded
away from some value). We show that if $f(x\land y)=f(x)\land f(y)$ with
probability larger than $s_{\land}\approx 0.815$ then $f$ correlates with some
low-degree character, and $s_{\land}$ is the optimal threshold for this
property.

Our result generalize the classical linearity testing result of Blum, Luby and
Rubinfeld, that in this language showed that the approximate polymorphisms of
$g=\mathsf{XOR}$ are close to XOR’s, as well as a recent result of Filmus,
Lifshitz, Minzer and Mossel, showing that the approximate polymorphisms of AND
can only be close to AND functions.

##  1 Introduction

Let $m\in\mathbb{N}$ be thought of as a constant, $n\in\mathbb{N}$ be thought
of as large, and let $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ be any function. We
say that $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a _polymorphism_ of $g$ if
their operations commute. More precisely, defining the functions $f\circ
g^{n},g\circ f^{m}\colon\\{0,1\\}^{n\times m}\to\\{0,1\\}$ as

$(f\circ
g^{n})(Z)=f(g(\mathsf{row}_{1}(Z)),\ldots,g(\mathsf{row}_{n}(Z))),\qquad(g\circ
f^{m})(Z)=g(f(\mathsf{col}_{1}(Z)),\ldots,f(\mathsf{col}_{m}(Z))),$

we say that $f$ is a polymorphism of $g$ if $f\circ g^{n}=g\circ f^{m}$. See
Figure 1 for an illustration.

$\begin{array}[]{|c|c|c|c|c|}\cline{1-3}\cr\cline{5-5}\cr
Z_{11}&\cdots&Z_{1m}&\stackrel{{\scriptstyle
g}}{{\to}}&g(\mathsf{row}_{1}(Z))\\\
\cline{1-3}\cr\cline{5-5}\cr\vdots&\ddots&\vdots&\raisebox{2.0pt}{$\stackrel{{\scriptstyle
g}}{{\to}}$}&\vdots\\\ \cline{1-3}\cr\cline{5-5}\cr
Z_{n1}&\cdots&Z_{nm}&\stackrel{{\scriptstyle
g}}{{\to}}&g(\mathsf{row}_{n}(Z))\\\
<EMAIL_ADDRESS>f$}\hfil\lx<EMAIL_ADDRESS>f$}\hfil\lx<EMAIL_ADDRESS>f$}\hfil\lx@intercol&\lx@intercol\hfil\hfil\lx<EMAIL_ADDRESS>f$}\hfil\lx@intercol\\\ \cline{1-3}\cr\cline{5-5}\cr
f(\mathsf{col}_{1}(Z))&\cdots&f(\mathsf{col}_{m}(Z))&\stackrel{{\scriptstyle
g}}{{\to}}&\ast\\\ \cline{1-3}\cr\cline{5-5}\cr\end{array}$ Figure 1: $f$ is a
polymorphism of $g$, in symbols $f\circ g^{n}=g\circ f^{m}$, if applying $g$
to the bottom row produces identical results to applying $f$ to the rightmost
column.

More generally, for a parameter $\delta>0$, we say that $f$ is a _$\delta$
-approximate polymorphism_ if

$\Pr_{Z}[(f\circ g^{n})(Z)\neq(g\circ f^{m})(Z)]\leqslant\delta;$

here and throughout, the distribution over $Z$ is uniform over
$\\{0,1\\}^{n\times m}$. We note that for any function $g$, one always has
dictatorship functions as polymorphisms. Namely, for each $j\in[n]$, it is
easily seen that the function $f(x)=x_{j}$ is a polymorphism of $g$ as

$(f\circ g^{n})(Z)=g(\mathsf{row}_{j}(Z))=(g\circ f^{m})(Z).$

Dictatorship polymorphisms will thus be referred to as _trivial polymorphisms_
of $g$. If $g$ possesses a mild structural property, then there are additional
trivial polymorphisms: when $g$ is odd, anti-dictatorships also form
polymorphisms; if $g(b,\ldots,b)=b$, then the constant function $f(x)=b$ also
forms a polymorphism. What can be said about the structure of functions $g$
that have non-trivial polymorphisms? More generally, what can be said about
functions $g$ that have approximate polymorphisms that are far from being
trivial? Furthermore, can we classify the structure of the approximate
polymorphisms in these cases?

The problem of studying the structure of polymorphisms as well as approximate
polymorphisms has appeared in several different contexts throughout
theoretical computer science:

  1. 1.

Universal algebra and the complexity of constraint satisfaction problems. In
this context, the function $g$ is allowed to be a predicate rather than a
function, and a polymorphism is a function $f$ that takes satisfying
assignments to $g$, ordered as rows in the matrix $Z\in\\{0,1\\}^{n}$, and
produces a satisfying assignment for $g$ in the form $f^{m}(Z)$ (i.e.,
somewhat of a one-sided version of the above equation). In this context, the
existence of non-trivial polymorphisms is strongly linked to the complexity of
the constraint satisfaction problem corresponding to the predicate $g$ (see
for example [BKW17]).

  2. 2.

Property testing. Perhaps the most basic problem in property testing, the
linearity testing problem [BLR90, BCH+96], can be cast in the language of
approximate polymorphisms. Here, one takes $m=2$ and the function
$g(x,y)=x\oplus y$, in which case a function $f$ is an $\delta$ approximate
polymorphism if $f(x\oplus y)=f(x)\oplus f(y)$ with probability $\geqslant
1-\delta$, where $x$ and $y$ are sampled uniformly and independently from
$\\{0,1\\}^{n}$. This question, as well as its $\nicefrac{{1}}{{2}}+\delta$
list-decoding variant have been well studied and are useful in the study of
PCP’s [Hås01].

  3. 3.

Social choice theory. In this context, one thinks of the functions $f,g$ as
voting rules, and then the above functions $f\circ g^{n}$, $g\circ f^{m}$ can
be thought of as two ways of aggregating these voting rules in order to reach
a final outcome. Due to this interpretation, it makes sense to also consider
the “cross” version of the problem, wherein we have multiple functions $f$,
say $f_{0},\ldots,f_{m}$, and we replace the above equation by

$(f_{0}\circ
g^{n})(Z)=g(f_{1}(\mathsf{col}_{1}(Z)),\ldots,f_{m}(\mathsf{col}_{m}(Z))).$

The interpretation here is that there are $n$ voters that cast their yes/ no
opinion on each one of $m$ topics; notationally, the vector
$\mathsf{row}_{i}(Z)$ represents the opinions of voter $i$. The goal is to
aggregate these opinions about the topic to reach a final conclusion, and
naturally this can be done in one of two ways: first, one may aggregate the
opinion of each voter, and then aggregate the final conclusion of each voter.
This way of aggregation is represented by $(f_{0}\circ g^{n})(Z)$. Another way
to aggregate these opinions is to first reach a final conclusion regarding
each topic, which is $f_{j}(\mathsf{col}_{j}(Z))$ in the above notation, and
then aggregate those; this is represented by the function
$g(f_{1}(\mathsf{col}_{1}(Z)),\ldots,f_{m}(\mathsf{col}_{m}(Z)))$. Thus, in
this interpretation, the question asks for which aggregation rules $g$ and
$f_{i}$ does it hold that the two natural ways of aggregating the votes are
essentially equivalent.

The case where $g$ is an AND function is a prominent example that has been
studied in this context. In particular, the fact that $f={\sf Majority}$ does
not yield equivalent rules is known as the _Doctrinal paradox_ , which raised
the question of what are all $f$’s in this case that yield equivalent rules.
This problem has been addressed by Nehama [Neh13] in the context of social
choice theory and by Parnas, Ron and Samorodnitsky [PRS02] from the property
testing point of view, and both works establishing partial results. A recent
work [FLMM20] has improved these results, showing that in this case the
approximate polymorphisms of $g$ can only be functions that are close to AND
functions.

With this in mind, it makes sense to ask what is the most general result one
can prove when $g$ is a general function on constantly many coordinates.
Indeed, answering this question is the main goal of this paper:

Determine all pairs $f,g$ which are _approximate polymorphisms_ : $\Pr[f\circ
g^{n}=g\circ f^{m}]\geqslant 1-\delta.$

###  1.1 The structure of exact polymorphisms

The exact polymorphisms variant of this problem, i.e. the case that
$\delta=0$, has been previously studied by Dokow and Holzman [DH09]. They
manage to give the following tight classification of all possible pairs $f,g$
in which $f$ is a polymorphism of $g$:

  1. 1.

One of $f,g$ is constant, a dictator ($x_{i}$), or an anti-dictator ($\lnot
x_{i}$).

  2. 2.

$f,g$ are XORs or their negation.

  3. 3.

$f,g$ are ANDs.

  4. 4.

$f,g$ are ORs.

Stated otherwise, the only $g$’s that have non-trivial polymorphisms are
AND’s, OR’s, XOR’s and NXOR’s. It is interesting to note that in each one of
these cases, the answer to the approximate polymorphisms problem has already
been resolved; the case $g$ is an XOR or an NXOR is linearity testing [BLR90,
BCH+96], and it is well-known that $f$ must be close to an XOR or its
negation. When $g$ is an AND, it was shown in [FLMM20] that $f$ is close to
zero or to an AND, and the case where $g$ is an OR is similar.

Thus, it would be natural to guess that the only $g$’s that have non-trivial
approximate polymorphisms would be exactly the $g$’s found by Dokow and
Holzman. Furthermore, we would expect that if $g$ is not an XOR, NXOR, AND, or
OR, and $f$ is an approximate polymorphism, then $f$ must be trivial, i.e.
close to a constant, a dictator, or an anti-dictator. Here and throughout,
closeness is measured with respect to the Hamming distance over the uniform
measure on $\\{0,1\\}^{n}$.

###  1.2 Main results

####  1.2.1 Approximate polymorphisms

In this language, our main result reads:

######  Theorem 1.1.

Fix $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$. For every $\varepsilon>0$ there exists
$\delta>0$ (depending on both $g$ and $\varepsilon$) such that if
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ satisfies

$\Pr_{Z}[(f\circ g^{n})(Z)=(g\circ f^{m})(Z)]\geqslant 1-\delta,$

then either:

  1. 1.

$f$ is $\varepsilon$-close to a constant, dictator, anti-dictator or an exact
polymorphism of $g$;

  2. 2.

$g$ is either an NOR or an NAND, and $f$ is $\varepsilon$-close to an OR or an
AND (respectively).

Naively, one may have hoped that the first item in the theorem must always
hold, however as we explain next, it is necessary to include the second item
as well. Suppose that $g$ is unbalanced, so that
$p=\operatorname*{\mathbb{E}}[g]$ is at least $2^{-m}$-far from $1/2$. Suppose
we have functions $f_{0}$ and $f_{1}$ satisfying $f_{0}\circ g^{n}=g\circ
f_{1}^{m}$. Given such $f_{0},f_{1}$, we may construct a function $f$ agreeing
with $f_{1}$ around the middle slice and with $f_{0}$ around the $pn$-slice,
and have that $f\circ g^{n}\approx g\circ f^{m}$. All new solutions in Theorem
1.1 arise from such _skew polymorphisms_.

Dokow and Holzman in fact solved the more general cross version of the problem
defined above. Namely, they managed to classify all solutions to the equation
$f_{0}\circ g^{n}=g\circ(f_{1},\ldots,f_{m})$. Our main result extends to this
setting as well, and we prove an analog of Theorem 1.1 for it as well (see
Theorem 4.1 for a precise statement).

We also provide an alternative proof of the classification of Dokow and
Holzman [DH09], using Boolean function analysis. To illustrate the merits of
this proof technique, we classify all solutions of the slightly more general
equation

$f_{0}\circ g^{n}=h\circ(f_{1},\ldots,f_{m}).$

####  1.2.2 The list decoding regime

As discussed earlier, the linearity testing problem, which constitutes one
example of the approximate polymorphisms problem, can be studied in several
different regimes:

  1. 1.

Exact regime: If $\Pr[f(x\oplus y)=f(x)\oplus f(y)]=1$ then $f$ is an XOR.

  2. 2.

Approximate regime: If $\Pr[f(x\oplus y)=f(x)\oplus f(y)]\geqslant 1-\delta$
then $f$ is $O(\delta)$-close to an XOR.

  3. 3.

List decoding regime: If $\Pr[f(x\oplus y)=f(x)\oplus f(y)]\geqslant
1/2+\delta$ then $f$ is $\Omega(\delta)$-correlated with some XOR.

In this language, Dokow and Holzman extended the exact regime to arbitrary
functions $g$ (in linearity testing, $g(x,y)=x\oplus y$), and Theorem 1.1
extends the approximate regime to arbitrary functions $g$. Our second main
result extends the list decoding regime to arbitrary functions $g$.

######  Theorem 1.2.

Fix $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ which is not a constant, a dictator, or
an anti-dictator. There exists a constant $s_{g}<1$ such that the following
holds:

  1. 1.

For every $\varepsilon>0$ there exists $\delta>0$ such that if

$\Pr_{Z}[(f\circ g^{n})(Z)=(g\circ f^{m})(Z)]\geqslant s_{g}+\delta$

then $f$ is $\varepsilon$-correlated with some XOR.

  2. 2.

For every $\delta>0$, there exists large enough $n$ and a function
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ such that the correlation of $f$ with any
XOR is at most $\delta$, and

$\Pr_{Z}[(f\circ g^{n})(Z)=(g\circ f^{m})(Z)]\leqslant s_{g}-\delta.$

Computing the value of $s_{g}$ may be a challenging task in general. In the
case that $g$ is an XOR, one has $s_{g}=1/2$. When $g(x,y)=x\land y$, one may
have expected $s_{g}$ to be equal to $3/4$ (as was conjectured by [FLMM20]).
It turns out that it is actually higher, about $0.814975$.

####  1.2.3 Comparison to previous work

Our main theorems generalize classical work on linearity testing [BLR90,
BCH+96], which is the special case of $g=\mathsf{XOR}$.

This work was prompted by recent work [FLMM20] which proved Theorem 1.1 in the
special case of $g=\mathsf{AND}$. Theorem 1.1 and Theorem 1.2 answer two of
the three open questions posed in [FLMM20].

Several other results in the literature can be seen as analogs of Theorem 1.1
in the more general case of predicates:

  1. 1.

Arrow’s theorem. The $\mathsf{NAE_{3}}$ predicate is a predicate on triples of
bits which holds whenever the three bits are not all equal. Arrow’s theorem
[Arr50] for three candidates states, in our language, that the only
polymorphisms of $\mathsf{NAE_{3}}$ satisfying $f(0,\ldots,0)=0$ and
$f(1,\ldots,1)=1$ are dictators. Wilson [Wil72] improved this, showing that
the only polymorphisms of $\mathsf{NAE_{3}}$ are dictators and anti-dictators.
Mossel [Mos12], improving on earlier work of Kalai [Kal02], showed that
approximate polymorphisms of $\mathsf{NAE_{3}}$ are close to dictators or to
anti-dictators. Mossel’s result is more general, allowing for more than three
candidates.111Mossel’s result is even more general, classifying also exact and
approximate _multi-_ polymorphisms, in which different $f$’s are allowed for
different columns. Mossel’s work was subsequently improved quantitatively by
Keller [Kel12].

  2. 2.

Intersecting families. An intersecting family is the same as a polymorphism of
the binary predicate $\mathsf{NAND_{2}}$ on pairs of bits. We define
approximate polymorphisms of $\mathsf{NAND_{2}}$ with respect to the unique
distribution $\mu_{p,p}$ supported on the support of $\mathsf{NAND}_{2}$ whose
marginals are $\mu_{p}$.
Friedgut and Regev [FR18] proved, in our language, that when $p<1/2$, any
approximate polymorphism of $\mathsf{NAND_{2}}$ is close to an exact
polymorphism of $\mathsf{NAND_{2}}$.

###  1.3 Techniques: thm:main-intro

The proof of Theorem 1.1 is composed of two parts. First, we show that $f$ is
close to a junta. Second, we use this to reduce the approximate question to an
_exact_ question.

We can assume without loss of generality that $g$ depends on all coordinates.
If $g$ is an XOR or an NXOR then Theorem 1.1 reduces to linearity testing
(except for the trivial cases $m=0$ and $m=1$), and so we can assume that $g$
is not an XOR or an NXOR. This implies that $g$ has an input $\alpha$ with a
nonsensitive coordinate $j$, that is, $g(\alpha)=g(\alpha^{\oplus j})$, where
$\alpha^{\oplus j}$ results from flipping the $j$th coordinate. To simplify
notation, we assume that $j=m$.

####  1.3.1 Showing that $f$ is close to a junta

##### The basic argument

In this part, we assume that $(f\circ g^{n})(Z)=(g\circ f^{m})(Z)$ with
probability at least $1-\eta$. Later on, we will choose $\delta$ as a function
of both $\eta$ and the size of the junta.

Suppose first that $f$ has no influential variables. In this case, we will
show that $f$ is $\varepsilon$-close to a constant function. We do this by
assuming that $f$ is $\varepsilon$-far from constant and reaching a
contradiction.

The idea is to construct two correlated inputs $Z,W$, each individually
uniformly random, such that

$(f\circ g^{n})(Z)=(f\circ g^{n})(W)$

with probability $1$. To sample such $Z,W$, we use the input $\alpha$. Namely,
we form $W$ by resampling the $m$th coordinate of each row whose first $m-1$
coordinates agree with $\alpha$. Thus, by the approximate polymorphism
condition, it follows that $(g\circ f^{m})(Z)=(g\circ f^{m})(W)$ with
probability $\geqslant 1-2\eta$; as we argue next, this last fact will tell us
that $f$ must be close to constant.

Since $g$ depends on all coordinates, there is an input $\beta$ such that
$g(\beta)\neq g(\beta\oplus e_{m})$; suppose without loss of generality that
$g(\beta_{1},\ldots,\beta_{m-1},x_{m})=x_{m}$. By assumption, $f$ is
$\varepsilon$-far from constant, and so with probability at least
$\varepsilon^{m-1}$, if we evaluate $f$ on the first $m-1$ columns of $Z$
(which are identical to the corresponding columns of $W$) then we obtain
$\beta_{1},\ldots,\beta_{m-1}$. When this happens,

$(g\circ f^{m})(Z)=f(\mathsf{col}_{m}(Z))\text{ and }(g\circ
f^{m})(W)=f(\mathsf{col}_{m}(W)),$

and we get that $f(\mathsf{col}_{m}(Z))=f(\mathsf{col}_{m}(W))$ with
probability $\geqslant 1-2\eta$. To analyze this event, we consider the
following equivalent way of sampling $z=\mathsf{col}_{m}(Z)$ and
$w=\mathsf{col}_{m}(W)$:

  1. 1.

Sample a subset $R\subseteq[n]$ by including each element with probability
$2^{-(m-1)}$; these are the rows whose first $m-1$ columns agree with
$\alpha$.

  2. 2.

Sample $z_{j}=w_{j}$ for each $j\notin R$.

  3. 3.

Sample $z_{j},w_{j}$ independently for each $j\in R$.

The first two steps define a random restriction, and to reach a contradiction
we would like to argue that this random restriction still has a significant
variance with high probability (so that we will in fact have $f(z)\neq f(w)$
with significant probability). Indeed, this is true provided the variance of
$f$ is significant and all of the (low-degree) influences of $f$ are small;
this is the so-called “It Ain’t Over Till It’s Over” theorem from [MOO10]. A
bit more precisely, this result asserts that provided the influences of $f$
are small, it is extremely likely (the failure probability is smaller than
$\varepsilon^{m-1}/2$) that $f$ is $\gamma$-far from constant even after the
random restriction, where $\gamma(\varepsilon,m)>0$. This gives us that

$\Pr[(g\circ f^{m})(Z)\neq(g\circ
f^{m})(W)]\geqslant\left(\varepsilon^{m-1}-\frac{\varepsilon^{m-1}}{2}\right)\cdot
2\gamma(1-\gamma).$

Thus, choosing $\eta$ so that $2\eta$ is smaller than this expression, we
reach a contradiction. This contradiction thus implies that if all of the
influences of $f$ are small, then the only way for $f$ to be an approximate
polymorphism of $g$ is that $f$ is close to a constant.

##### Lifting the small low-degree influences assumption.

An arbitrary function $f$ could potentially have influential variables. To
generalize our argument to this case, we make use of a regularity lemma
[Jon16] by Jones. This lemma asserts that one may find a small set of
variables $T$ such that randomly restricting them in $f$, one gets a function
with no significant low-degree influences with probability close to $1$. Thus,
we first perform this random restriction, and then use a variant of the above
argument to argue that under such restrictions, $f$ must be in fact close to a
constant. Over all, we obtain that $f$ is close to a junta.

####  1.3.2 Deducing thm:main-intro

The previous part shows that $f$ is close to a junta $F$, say depending on the
first $L$ coordinates. We split the input $Z$ accordingly to two matrices:
$Z^{(1)}$ consists of the first $L$ rows, and $Z^{(2)}$ consists of the
remaining rows. Thus with probability $1-\delta$,

$f(g(\mathsf{row}_{1}(Z^{(1)})),\ldots,g(\mathsf{row}_{L}(Z^{(1)})),g(\mathsf{row}_{1}(Z^{(2)})),\ldots,g(\mathsf{row}_{n-L}(Z^{(2)})))=\\\
g(f(\mathsf{col}_{1}(Z^{(1)}),\mathsf{col}_{1}(Z^{(2)})),\ldots,f(\mathsf{col}_{m}(Z^{(1)}),\mathsf{col}_{m}(Z^{(2)}))).$

If we fix $Z^{(2)}$ then we can find functions
$f_{0},\ldots,f_{m}\colon\\{0,1\\}^{L}\to\\{0,1\\}$ such that the left-hand
side becomes $f_{0}\circ g$, and the right-hand side becomes
$g\circ(f_{1},\ldots,f_{m})$.

For a typical $Z^{(2)}$, the functions $f_{1},\ldots,f_{m}$ are all close to
$F$ and so to each other, and furthermore

$\Pr[f_{0}\circ g^{n}\neq g\circ(f_{1},\ldots,f_{m})]\leqslant\delta.$

We choose $\delta<\min(\eta,2^{-mL})$, and so this implies that in fact,

$f_{0}\circ g^{n}=g\circ(f_{1},\ldots,f_{m}).$

Since the functions $f_{1},\ldots,f_{m}$ are close to each other, the
classification of all solutions to the equation $f_{0}\circ
g=g\circ(f_{1},\ldots,f_{m})$ implies that $f_{1}=\cdots=f_{m}$ (except for
some corner cases), and so $f_{0}\circ g=g\circ f_{1}$. This completes the
proof, since both $f_{1}$ and $f$ are close to $F$.

###  1.4 Techniques: thm:list-decoding-intro

We illustrate the proof of the theorem in the special case of the AND
function. It will be more convenient to switch from $\\{0,1\\}$ to
$\\{-1,1\\}$, and to consider $g(x_{1},x_{2})=x_{1}\land
x_{2}=\min(x_{1},x_{2})$ (which is one possible interpretation of AND).

We prove the theorem in contrapositive: assuming that all low-degree Fourier
coefficients are small (which is equivalent to having small correlation with
all XORs), we will bound $\Pr[f(x\land y)=f(x)\land f(y)]$, or rather
$\operatorname*{\mathbb{E}}[f(x\land y)(f(x)\land f(y))]$ (this is one reason
to switch to $\\{-1,1\\}$).

The main idea is to apply the invariance principle in order to switch to a
problem in Gaussian space. For this, we need $f$ to have small low-degree
influences, as well as low degree. We can assume that $f$ has small low-degree
influences by appealing to Jones’ regularity lemma. In order to reduce the
degree of $f$, we apply a small amount of noise. An expansion argument of
Mossel [Mos10] shows that the noise doesn’t affect the expectation by much,
essentially since given $x$ and $x\land y$ there is some uncertainty regarding
$y$.

What do we get in Gaussian space? The vector

$\frac{(x\land y)+1/2}{\sqrt{3/4}},x,y$

has expectation zero and covariance matrix

$\Sigma=\begin{pmatrix}1&\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{3}}\\\
\frac{1}{\sqrt{3}}&1&0\\\ \frac{1}{\sqrt{3}}&0&1\end{pmatrix}.$

This shows that for some functions $q,p\colon\mathbb{R}^{n}\to\mathbb{R}$,

$\operatorname*{\mathbb{E}}[f(x\land y)(f(x)\land
f(y))]\approx\operatorname*{\mathbb{E}}[q(\mathcal{G}_{0})(p(\mathcal{G}_{1})\land
p(\mathcal{G}_{2}))],$

where $(\mathcal{G}_{0},\mathcal{G}_{1},\mathcal{G}_{2})$ is a multivariate
Gaussian with expectation zero and covariance $\Sigma$, and
$p(\mathcal{G}_{1})\land
p(\mathcal{G}_{2})=(-1+p(\mathcal{G}_{1})+p(\mathcal{G}_{2})+p(\mathcal{G}_{1})p(\mathcal{G}_{2}))/2$
is the multilinear extension of $\land$. Due to the degree-reducing noise, $p$
depends mostly on the behavior of $f$ around the middle slice, and $q$ depends
mostly on its behavior around the quarter slice. A standard truncation
argument lets us assume that $q,p$ attain values in $[-1,1]$, and a further
rounding argument lets us assume that they attain values in $\\{-1,1\\}$.

The assumption that $f$ has no large low-degree Fourier coefficients
translates to $\operatorname*{\mathbb{E}}[p]\approx 0$.222Due to the
application of Jones’ regularity lemma, we are actually working with
restrictions of $f$ rather than $f$ itself. In order to ensure that these
restrictions have expectation close to zero, we need to assume that $f$ has
small lower-degree Fourier coefficients. We do not have control over
$\operatorname*{\mathbb{E}}[q]$, since it is controlled by the low-degree
Fourier coefficients of $f$ with respect to the $\\{-1,1\\}$-analog of
$\mu_{1/4}$. Applying a generalization of Borell’s theorem due to Neeman
[Nee14], this is enough to show that the optimal choice for $p$ is the one-
dimensional sign function. By calculating the corresponding optimal choice for
$q$, we obtain

$\Pr[f(x\land y)=f(x)\land f(y)]\lesssim 0.814975356673002.$

Here is a matching construction: take $f$ to be the majority function for
inputs $x$ such that $\frac{1}{n}\sum_{i}x_{i}\approx 0$, and an appropriate
threshold function elsewhere. The construction exploits the fact that random
points $x,y\in\\{-1,1\\}^{n}$ satisfy
$\frac{1}{n}\sum_{i}x_{i},\frac{1}{n}\sum_{i}y_{i}\approx 0$ while
$\frac{1}{n}\sum_{i}(x_{i}\land y_{i})\approx-\frac{1}{2}$. Choosing the
optimal threshold gives a function $f$ with

$\Pr[f(x\land y)=f(x)\land f(y)]\gtrsim 0.814975356673002.$

###  1.5 Techniques: Classifying exact (multi-)polymorphisms

Dokow and Holzman [DH09] classified all exact multi-polymorphisms, that is,
all exact solutions to the equation $f_{0}\circ
g^{n}=g\circ(f_{1},\ldots,f_{m})$, using combinatorial arguments. We present
an alternative proof using Boolean function analysis in Section 6. For the
sake of the proof, we switch from $\\{0,1\\}$ to $\\{-1,1\\}$.

The proof proceeds in two main steps. In the first step, we determine all
multilinear polynomials $g,h\colon\\{-1,1\\}^{m}\to\mathbb{R}$ and
$f_{0},\ldots,f_{m}\colon\\{-1,1\\}^{n}\to\mathbb{R}$ which solve the equation

$f_{0}(g(z_{11},\ldots,z_{1m}),\ldots,g(z_{n1},\ldots,z_{nm}))=h(f_{1}(z_{11},\ldots,z_{n1}),\ldots,f_{m}(z_{1m},\ldots,z_{nm})),$

where the functions $f_{0},\ldots,f_{m},g,h$ are extended to $\mathbb{R}^{n}$
or $\mathbb{R}^{m}$ multilinearly. Except for some corner cases, these
solutions all involve functions of the form

$A\prod_{i\in S}(x_{i}+\kappa_{i})-B.$

In the second step, we observe that a function of the form above is Boolean
iff it corresponds to either XOR, NXOR, AND, or OR, which completes the
classification.

The first step is itself composed of two substeps. In the first substep, we
relate the supports of the Fourier expansions of $g,h,f_{0},\ldots,f_{m}$ to
that of $f_{0}\circ g$ and $g\circ(f_{1},\ldots,f_{m})$, and conclude that
except for some corner cases, and after possibly removing irrelevant
coordinates, $\deg g=\deg h=m$ and $\deg f_{0}=\deg f_{1}=\cdots=\deg
f_{m}=n$. In the second step, we show that up to affine shifts, the only
solution to $f_{0}\circ g^{n}=h\circ(f_{1},\ldots,f_{m})$ is
$g(y)=h(y)=\prod_{j=1}^{m}y_{j}$ and
$f_{0}(x)=f_{1}(x)=\cdots=f_{m}(x)=\prod_{i=1}^{m}x_{i}$.

##### Paper organization

After a few preliminaries in Section 2, we prove Theorem 1.1 in Section 3, and
its generalization to the setting of several $f$’s in Section 4. We discuss
the list decoding regime in Section 5. Section 6 determines all solutions to
the equation $f_{0}\circ g^{n}=h\circ(f_{1},\ldots,f_{m})$. We close the paper
with Section 7, which poses several open questions.

##  2 Preliminaries

We assume that the reader is familiar with the rudiments of Boolean function
analysis, as described in the monograph [O’D14].

We use $[n]$ for $\\{1,\ldots,n\\}$. If $v$ is a vector, $v|_{I}$ denotes its
restriction to the coordinates in $I$.

The low-degree influence is defined by $\operatorname{Inf}_{i}^{\leqslant
d}[f]=\operatorname{Inf}_{i}[f^{\leqslant d}]$. The distribution $\mu_{p}$ is
the product distribution over $\\{0,1\\}^{n}$ in which each coordinate equals
$1$ with probability $p$. We sometimes denote this distribution by
$\mu_{p}(\\{0,1\\}^{n})$. The distribution $\mathcal{N}(0,1)$ is a standard
normal distribution (zero mean, unit variance).

We use the notation $x^{\oplus n}$ for the $n$-fold XOR of $x$. That is,
$x^{\oplus n}=0$ if $x=0$ or $n$ is even, and $1^{\oplus n}=1$ if $n$ is odd.
The latter definition makes sense even when $n$ is negative.

A function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is _odd_ if $f(\lnot x)=\lnot
f(x)$, where $\lnot x=(\lnot x_{1},\ldots,\lnot x_{n})$, and _even_ if
$f(\lnot x)=f(x)$. The function $f$ is _balanced_ if
$\operatorname*{\mathbb{E}}[f]=1/2$.

Two Boolean functions $f,g\colon\\{0,1\\}^{n}\to\\{0,1\\}$ are _$\varepsilon$
-close_ if $\Pr[f\neq g]\leqslant\varepsilon$. The functions are
_$\varepsilon$ -close with respect to $\mu_{p}$_ if $\Pr_{\mu_{p}}[f\neq
g]\leqslant\varepsilon$.

A function $f$ is a _$J$ -junta_ if it depends on at most $J$ coordinates (if
$J\in\mathbb{N}$), or if it depends on the coordinates in $J$ (if $J$ is a
set).

Unless stated otherwise, random variables ranging over $\\{0,1\\}^{n}$ take
the uniform distribution $\mu_{1/2}$.

Various results will start by fixing some parameters. Any subsequent big $O$
bounds will depend on these parameters.

###  2.1 Polymorphisms

We start by formally defining polymorphisms. First, we define some required
notation.

######  Definition 2.1 (Composition).

Let $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ and $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$.
We define functions $f\circ g^{n}\colon\\{0,1\\}^{nm}\to\\{0,1\\}$ and $g\circ
f^{m}\colon\\{0,1\\}^{nm}\to\\{0,1\\}$, whose input is an $n\times m$ matrix
$Z$, by

$\displaystyle(f\circ g^{n})(Z)$
$\displaystyle=f(g(\mathsf{row}_{1}(Z)),\ldots,g(\mathsf{row}_{n}(Z))),$
$\displaystyle(g\circ f^{m})(Z)$
$\displaystyle=g(f(\mathsf{col}_{1}(Z)),\ldots,f(\mathsf{col}_{m}(Z))).$

If $f_{1},\ldots,f_{m}\colon\\{0,1\\}^{m}\to\\{0,1\\}$, we also define
$g\circ(f_{1},\ldots,f_{m})\colon\\{0,1\\}^{nm}\to\\{0,1\\}$ by

$(g\circ(f_{1},\ldots,f_{m}))(Z)=g(f_{1}(\mathsf{col}_{1}(Z)),\ldots,f_{m}(\mathsf{col}_{m}(Z))).$

We can now define polymorphisms and their generalization, skew-polymorphisms
and multi-polymorphisms.

######  Definition 2.2 (Polymorphisms).

A function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a _polymorphism_ of a
function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ if

$f\circ g^{n}=g\circ f^{m}.$

The pair $f_{0},f_{1}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ forms a _skew
polymorphism_ of a function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ if

$f_{0}\circ g^{n}=g\circ f_{1}^{m}.$

A tuple $f_{0},\ldots,f_{m}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ forms a _multi-
polymorphism_ of $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ if

$f_{0}\circ g^{n}=g\circ(f_{1},\ldots,f_{m}).$

The function $f$ is an _$\varepsilon$ -approximate_ polymorphism of $g$ if

$\Pr[f\circ g^{n}=g\circ f^{m}]\geqslant 1-\varepsilon.$

We define approximate versions of the other notions in a similar way.

Dokow and Holzman [DH09] essentially characterized all multi-polymorphisms (a
result which we reprove in this paper). Let us first state the resulting
characterization of polymorphisms.

######  Theorem 2.3.

If $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a polymorphism of
$g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ then one of the following cases holds:

  * •

$g=b$ is constant and $f(b,\ldots,b)=b$, or $f=b$ is constant and
$g(b,\ldots,b)=b$.

  * •

$g=x_{i}$ and $f$ is arbitrary, or $f=x_{i}$ and $g$ is arbitrary.

  * •

$g=\lnot x_{i}$ and $f$ is odd, or $f=\lnot x_{i}$ and $g$ is odd.

  * •

There exist $I\subseteq[n]$ and $J\subseteq[m]$ such that
$f(x)=\bigoplus_{i\in I}x_{i}\oplus a$, $g(x)=\prod_{j\in J}x_{j}\oplus b$,
and $a^{\oplus(|J|-1)}=b^{\oplus(|I|-1)}$.

  * •

There exist $I\subseteq[n]$ and $J\subseteq[m]$ such that $f(x)=\bigvee_{i\in
I}x_{i}$ and $g(x)=\bigvee_{j\in J}x_{j}$.

  * •

There exist $I\subseteq[n]$ and $J\subseteq[m]$ such that
$f(x)=\bigwedge_{i\in I}x_{i}$ and $g(x)=\bigwedge_{j\in J}x_{j}$.

The characterization of skew polymorphisms has a few more cases.

######  Theorem 2.4.

If $f_{0},f_{1}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a skew polymorphism of
$g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ then one of the following cases holds:

  * •

$g(x)=b$ is constant and $f_{0}(b,\ldots,b)=b$, or $f_{0}=a_{0}$ and
$f_{1}=a_{1}$ are constants and $g(a_{1},\ldots,a_{1})=a_{0}$.

  * •

$g(x)=x_{j}$ and $f_{0}=f_{1}$, or $f_{0}(x)=f_{1}(x)=x_{i}$.

  * •

$g(x)=\lnot x_{j}$ and $f_{0}(\lnot x)=\lnot f_{1}(x)$.

  * •

$f_{0}(x)=f_{1}(x)=\lnot x_{i}$ and $g$ is odd.

  * •

$f_{0}(x)=x_{i}$, $f_{1}(x)=\lnot x_{i}$, and $g$ is even.

  * •

There exist $I\subseteq[n]$ and $J\subseteq[m]$ such that
$f_{0}(x)=\bigoplus_{i\in I}x_{i}\oplus a_{0}$, $f_{1}(x)=\bigoplus_{i\in
I}x_{i}\oplus a_{1}$, $g(x)=\bigoplus_{j\in J}x_{j}\oplus b$, and $a_{0}\oplus
b^{\oplus(|I|-1)}=a_{1}^{\oplus|J|}$.

  * •

There exist $I\subseteq[n]$ and $J\subseteq[m]$ such that
$f_{0}(x)=f_{1}(x)=\bigvee_{i\in I}x_{i}$ and $g(x)=\bigvee_{j\in J}x_{j}$.

  * •

There exist $I\subseteq[n]$ and $J\subseteq[m]$ such that
$f_{0}(x)=\bigvee_{i\in I}x_{i}$, $f_{1}(x)=\bigwedge_{i\in I}x_{i}$, and
$g(x)=\bigvee_{j\in J}\lnot x_{j}$.

  * •

Same as preceding two cases, with $\bigvee$ and $\bigwedge$ switched.

The characterization of multi-polymorphisms has even more cases.

######  Theorem 2.5.

If $f_{0},\ldots,f_{m}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a multi-polymorphism
of $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ then one of the following cases holds:

  * •

$g=b$ is constant, and $f_{0}(b,\ldots,b)=b$.

  * •

$g=x_{i}$ and $f_{0}=f_{i}$.

  * •

$g=\lnot x_{i}$ and $f_{0}(\lnot x)=\lnot f_{i}(x)$.

  * •

$f_{0}=b_{0}$ is constant, and there exists $J\subseteq[m]$ such that
$f_{j}=b_{j}$ is constant for $j\in J$, and $g(x)=b_{0}$ whenever
$x_{j}=b_{j}$ for all $j\in J$.

  * •

$f_{j}=x_{i}\oplus a_{j}$ for $j=0$ and all $j$ that $g$ depends on, where
$g(x_{1}\oplus a_{1},\ldots,x_{m}\oplus a_{m})=g(x_{1},\ldots,x_{m})\oplus
a_{0}$.

  * •

There exist $I\subseteq[n]$ and $J\subseteq[m]$ such that
$f_{j}(x)=\bigoplus_{i\in I}x_{i}\oplus a_{j}$ for $j=0$ and $j\in J$,
$g(x)=\bigoplus_{j\in J}x_{j}\oplus b$, and $a_{0}\oplus
b^{\oplus(|I|-1)}=\bigoplus_{j\in J}a_{j}$.

  * •

There exist $I\subseteq[n]$ and $J\subseteq[m]$ such that
$f_{0}(x)=\bigvee_{i\in I}x_{i}$, $g(x)=\bigvee_{j\in J}(x_{j}\oplus a_{j})$,
and for every $j\in J$, if $a_{j}=0$ then $f_{j}(x)=\bigvee_{i\in I}x_{i}$,
and if $a_{j}=1$ then $f_{j}(x)=\bigwedge_{i\in I}x_{i}$.

  * •

Same as preceding case, with $\bigvee$ and $\bigwedge$ switched.

###  2.2 Results from Boolean function analysis

We will need several results concerning random restrictions and regular
functions, which we first define.

######  Definition 2.6 (Restriction).

Let $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$, let $J\subseteq[n]$, and let
$z\in\\{0,1\\}^{\overline{J}}$. We define the _restriction_
$f_{\overline{J}\to z}\colon\\{0,1\\}^{J}\to\\{0,1\\}$ by

$f_{\overline{J}\to z}(y)=f(x),\text{ where }x_{j}=\begin{cases}z_{j}&\text{if
}j\notin J,\\\ y_{j}&\text{if }j\in J.\end{cases}$

######  Definition 2.7 (Random restriction).

A _$p$ -random restriction_ is a pair $(J,z)$, where $J\subseteq[n]$ (the
parameter $n$ will be clear from context) and $z\in\\{0,1\\}^{\overline{J}}$
are sampled as follows: every element in $[n]$ is included in $J$ with
probability $p$, and $z$ is chosen uniformly at random. We denote this
distribution by $\mathcal{R}_{p}$.

######  Definition 2.8 (Regularity).

A Boolean function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is _( $d,\tau)$-regular_
if $\operatorname{Inf}_{i}^{\leqslant d}[f]\leqslant\tau$ for all $i\in[n]$.

The first result is a regularity lemma due to Jones [Jon16]; see also [Mos20,
Lemma 2.7].

######  Theorem 2.9 ([Jon16]).

For all $d\in\mathbb{N}$ and $\tau,\varepsilon>0$ there exists
$L\in\mathbb{N}$ such that the following holds.

For every $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ we can find a set $T\subseteq[n]$
of at most $L$ coordinates such that

$\Pr_{z\in\\{0,1\\}^{T}}[f_{T\to z}\text{ is $(d,\tau)$-regular}]\geqslant
1-\varepsilon.$

Furthermore, the result holds with respect to any finite number of product
measures $\mu_{p_{1}},\ldots,\mu_{p_{\ell}}$. That is, we can find a set $T$
such that for each $i\in[\ell]$, the statement above holds when $z$ is sampled
according to $\mu_{p_{i}}$ and when regularity is defined with respect to
$\mu_{p_{i}}$.

We explain how to deduce this result from Jones’ argument in Appendix A.

The second result is the famous “It Ain’t Over Till It’s Over” theorem.

######  Theorem 2.10 ([MOO10]).

For all $\varepsilon_{1},\varepsilon_{2},p>0$ there exist $d\in\mathbb{N}$ and
$\tau,\delta>0$ such that if $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is
$(d,\tau)$-regular and $\mathsf{var}(f)\geqslant\varepsilon_{1}$ then

$\Pr_{(J,z)\sim\mathcal{R}_{p}}[\mathsf{var}(f_{\overline{J}\to
z})\geqslant\delta]\geqslant 1-\varepsilon_{2}.$

The third result states that noise-stable functions are close to constant.

######  Definition 2.11 (Noise sensitivity).

Let $p\in(0,1)$ and $\rho\in[0,1]$, and let
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$. The _noise sensitivity_ of $f$ with
respect to $\mu_{p}$ is

$\operatorname{NS}_{\rho}^{\mu_{p}}(f)=\Pr_{x,y\sim
N_{\rho}^{\mu_{p}}}[f(x)\neq f(y)],$

where $N_{\rho}^{\mu_{p}}$ is the following distribution: we sample
$x\sim\mu_{p}$, and for each $i\in[n]$ independently, with probability $\rho$
we let $y_{i}=x_{i}$, and otherwise we sample $y_{i}$ according to $\mu_{p}$.

######  Lemma 2.12.

Fix $p,\rho\in(0,1)$. If $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ satisfies
$\operatorname{NS}_{\rho}^{\mu_{p}}(f)\leqslant\varepsilon$ then $f$ is
$O(\varepsilon)$-close to a constant function.

###### Proof.

Define $F\colon\\{0,1\\}^{n}\to\\{-1,1\\}$ by $F(x)=(-1)^{f(x)}$. On the one
hand,

$\operatorname*{\mathbb{E}}_{x,y\sim
N_{\rho}^{\mu_{p}}}[F(x)F(y)]=1-2\operatorname{NS}_{\rho}^{\mu_{p}}(f)\geqslant
1-2\varepsilon,$

On the other hand, it is well-known that

$\operatorname*{\mathbb{E}}_{x,y\sim
N_{\rho}^{\mu_{p}}}[F(x)F(y)]=\sum_{d=0}^{n}\rho^{d}\|F^{=d}\|^{2}\leqslant(1-\mathsf{var}(F))+\rho\mathsf{var}(F)=1-(1-\rho)\mathsf{var}(F).$

It follows that $\mathsf{var}(F)=O(\varepsilon)$, and so $f$ is
$O(\varepsilon)$-close to a constant function. ∎

##  3 Approximate polymorphisms

In this section we prove the following result, which implies Theorem 1.1 by
simple case analysis.

######  Theorem 3.1.

Fix $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$, and let $p=\Pr[g=1]$. For every
$\varepsilon>0$ there exists $\delta>0$ (depending on both $g$ and
$\varepsilon$) such that if $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a
$\delta$-approximate polymorphism of $g$ then there exists a skew polymorphism
$f_{0},f_{1}$ of $g$ such that $f$ is $\varepsilon$-close to $f_{1}$ with
respect to $\mu_{1/2}$ and to $f_{0}$ with respect to $\mu_{p}$.

If $g$ is balanced then $f$ is moreover $\varepsilon$-close to a polymorphism
of $g$.

We can assume without loss of generality that $g$ depends on all coordinates
(we show this formally below). If $g$ is an XOR or NXOR, then the result is
either trivial (if $g$ depends on at most one coordinate), or follows from an
analysis in the style of linearity testing (if $g$ depends on at least two
coordinates). Therefore we concentrate on the case in which $g$ depends on all
coordinates and is neither an XOR nor an NXOR.

When $g$ is neither an XOR nor an NXOR, it must have a non-trivial certificate
$\alpha$.

######  Lemma 3.2.

Suppose that $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ depends on all coordinates,
and is not of the form $\bigoplus_{i=1}^{m}x_{i}\oplus b$.

After possibly reordering the coordinates of $g$, we can find $\alpha$ such
that

$g(\alpha_{1},\ldots,\alpha_{m-1},0)=g(\alpha_{1},\ldots,\alpha_{m-1},1).$

###### Proof.

If it is impossible to find such $\alpha$ even after reordering the
coordinates, then for every $x\in\\{0,1\\}^{m}$ and any $j\in[m]$ we have
$g(x)\neq g(x^{\oplus j})$, where $x^{\oplus j}$ is obtained from $x$ by
flipping the $j$th coordinate. Thus

$g(x_{1},\ldots,x_{m})=g(0,\ldots,0)\oplus\bigoplus_{j=1}^{m}x_{j},$

in contrast to the assumption. Therefore we can find the desired $\alpha$
after possibly reordering the coordinates. ∎

We can use the certificate $\alpha$ to show that if $f$ is an approximate
polymorphism of $g$, then $f$ is close to a junta.

######  Lemma 3.3.

Fix a function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ which depends on all
coordinates and is not of the form $\bigoplus_{i=1}^{m}x_{i}\oplus b$.

For every $\varepsilon>0$ there exist $L\in\mathbb{N}$ and $\eta>0$ such that
any $\eta$-approximate polymorphism of $g$ is $\varepsilon$-close to an
$L$-junta.

We prove Lemma 3.3 in Section 3.1. Let us see how it implies Theorem 3.1.

Lemma 3.3 requires $g$ to depend on all coordinates. Let us first dispense
with this requirement.

######  Lemma 3.4.

Suppose that Theorem 3.1 holds when $g$ depends on all coordinates. Then it
holds for all $g$.

###### Proof.

If $g$ depends only on the coordinates in some subset $J\subseteq[m]$, we can
find a function $G\colon\\{0,1\\}^{J}\to\\{0,1\\}$ such that $g(x)=G(x|_{J})$.
By assumption, Theorem 3.1 holds for $G$, say with some parameter $\delta$. We
will show that Theorem 3.1 holds for $g$ as well, with the same parameter
$\delta$.

If $f$ is a $\delta$-approximate polymorphism of $g$, then it is also a
$\delta$-approximate polymorphism of $G$. Theorem 3.1 shows that $f$ is
$\varepsilon$-close (in an appropriate sense) to a skew polymorphism of $G$,
which is also a skew polymorphism of $g$. ∎

Lemma 3.3 also requires $g$ not to be XOR or its negation. We first show how
to prove Theorem 3.1 under this restriction, and then handle all other cases.

######  Lemma 3.5.

Theorem 3.1 holds when $g$ depends on all coordinates and is not of the form
$\bigoplus_{i=1}^{m}x_{i}\oplus b$.

###### Proof.

Given $\varepsilon>0$ (which we assume is small enough), let $L\in\mathbb{N}$
and $\eta>0$ be the constants promised by Lemma 3.3. We choose
$\delta=\min(\varepsilon,\eta,2^{-mL}/3)$.

Let $f$ be a $\delta$-approximate polymorphism of $g$. According to Lemma 3.3,
$f$ is $\varepsilon$-close to an $L$-junta $F$, say depending on the
coordinates $I\subseteq[n]$. We also think of $F$ as a function
$F_{I}\colon\\{0,1\\}^{I}\to\\{0,1\\}$.

Let $W$ be a random $\overline{I}\times m$ zero-one matrix. With probability
at least $2/3$ over the choice of $W$,

$\Pr_{Z}[(f\circ g^{n})(Z)\neq(g\circ
f^{m})(Z)\mid\mathsf{row}_{i}(Z)=\mathsf{row}_{i}(W)\text{ for all
}i\in\overline{I}]<3\delta.$

For each $j\in[m]$, with probability at least $1-1/(2m)$ over the choice of
$W$,

$\Pr_{x\in\\{0,1\\}^{n}}[f(x)\neq F(x)\mid
x|_{\overline{I}}=\mathsf{col}_{j}(W)]<2m\varepsilon.$

Since $1/3+m\cdot 1/(2m)<1$, we can find $W$ so that all of these $m+1$ events
happen.

Using $W$, we define $m+1$ functions
$f_{0},\ldots,f_{m}\colon\\{0,1\\}^{I}\to\\{0,1\\}$ which will turn out to be
a multi-polymorphism of $g$:

  * •

For $j\in[m]$, we let $f_{j}$ be the restriction of $f$ obtained by fixing the
coordinates in $\overline{I}$ to the values $\mathsf{col}_{j}(W)$.

  * •

Similarly, $f_{0}$ is the restriction of $f$ obtained by fixing coordinate
$i\notin I$ to $g(\mathsf{row}_{i}(W))$.

By construction,

$\Pr_{Z\in\\{0,1\\}^{I\times[m]}}[f_{0}\circ g^{n}\neq
g\circ(f_{1},\ldots,f_{m})]<3\delta\leqslant 2^{-mL},$

and so $f_{0},\ldots,f_{m}$ is a multi-polymorphism of $g$.

Since all of $f_{1},\ldots,f_{m}$ are $O(\varepsilon)$-close to $F_{I}$, all
of them are $O(\varepsilon)$-close to each other, and moreover $f$ is
$O(\varepsilon)$-close to all of them.

According to Theorem 2.5, one of the following cases holds:

  1. 1.

$f_{0}=b_{0}$ is constant, and there exists $J\subseteq[m]$ such that
$f_{j}=b_{j}$ is constant for $j\in J$, and $g(x)=b_{0}$ whenever
$x_{j}=b_{j}$ for all $j\in J$.

  2. 2.

$f_{j}=x_{i}\oplus a_{j}$ for some $i\in I$ and $j\in\\{0,\ldots,m\\}$.

  3. 3.

$g(x)=\bigvee_{j=1}^{m}(x_{j}\oplus a_{j})$, and there exists $K\subseteq I$
such that $f_{0}(x)=\bigvee_{i\in K}x_{i}$ and for $j\in[m]$, if $a_{j}=0$
then $f_{j}(x)=\bigvee_{i\in K}x_{i}$, and if $a_{j}=1$ then
$f_{j}(x)=\bigwedge_{i\in K}x_{i}$.

  4. 4.

Same as preceding case, with $\bigvee$ and $\bigwedge$ switched.

If the first case holds then $J\neq\emptyset$ since $g$ is non-constant, and
so $f$ is $O(\varepsilon)$-close to some constant $a_{1}$. Let
$a_{0}=g(a_{1},\ldots,a_{1})$. With probability $1-O(\varepsilon)$, $(f\circ
g^{n})(Z)=(g\circ f^{m})(Z)=g(a_{1},\ldots,a_{1})=a_{0}$, and so $f$ is
$O(\varepsilon)$-close to $a_{0}$ with respect to $\mu_{p}$.

In all other cases, we observe that since $f_{1},\ldots,f_{m}$ are
$O(\varepsilon)$-close to each other, necessarily $f_{1}=\cdots=f_{m}$, and so
$f_{0},f_{1}$ is a skew polymorphism of $g$. This is clear in the second case.
In the third and fourth cases, we can assume that $|K|\geqslant 2$, since
otherwise we are in one of the first two cases. Then $f_{1}=\cdots=f_{m}$
follows from

$\Pr\left[\bigvee_{i\in K}x_{i}=\bigwedge_{i\in
K}x_{i}\right]=\frac{2}{2^{|K|}}\leqslant\frac{1}{2}.$

Clearly $f$ is $O(\varepsilon)$-close to $f_{1}$. It remains to show that $f$
is $O(\varepsilon)$-close to $f_{0}$ with respect to $\mu_{p}$. To see this,
note that with probability $1-O(\varepsilon)$,

$(f\circ g^{n})(Z)=(g\circ f^{m})(Z)=(g\circ f_{1}^{m})(Z)=(f_{0}\circ
g^{n})(Z).$

Finally, when $g$ is balanced, $f_{0}$ and $f_{1}$ are $O(\varepsilon)$-close,
and so a simple case analysis shows that $f_{0}=f_{1}$. Therefore $f_{1}$ is a
polymorphism of $g$. ∎

To complete the proof of Theorem 3.1, we show that it holds when $g$ is an XOR
or its negation. This includes the cases that $g$ is constant ($m=0$) or an
(anti-)dictator ($m=1$). When $m\neq 0$, the function $g$ is balanced, and so
it suffices to show that any approximate polymorphism of $g$ is close to an
exact polymorphism of $g$.

######  Lemma 3.6.

Theorem 3.1 holds when $g(x)=\bigoplus_{i=1}^{m}x_{i}\oplus b$.

###### Proof.

If $m=0$ then $g=b$, and so a $\delta$-approximate polymorphism $f$ of $g$
satisfies

$\Pr[f(b,\ldots,b)=b]\geqslant 1-\delta.$

For any $\delta<1$ this implies that $f(b,\ldots,b)=b$, and so $f$ is a
polymorphism of $g$.

If $m=1$ then $g=x_{j}$ or $g=\lnot x_{j}$. If $g=x_{j}$ then every function
is a polymorphism of $g$. If $g=\lnot x_{j}$ then a $\delta$-approximate
polymorphism $f$ of $g$ satisfies

$\Pr[f(\lnot x_{1},\ldots,\lnot x_{n})=\lnot f(x_{1},\ldots,x_{n})]\geqslant
1-\delta.$

In particular, if we define $F\colon\\{0,1\\}^{n}\to\\{0,1\\}$ by

$F(x)=\begin{cases}f(x)&\text{if }x_{j}=0,\\\ \lnot f(\lnot x)&\text{if
}x_{j}=1,\end{cases}$

then $F$ is odd and

$\Pr[f\neq F]=\frac{1}{2}\Pr[f(x)\neq F(x)\mid
x_{j}=1]=\frac{1}{2}\Pr[f(x)\neq\lnot f(\lnot x)\mid x_{j}=1]\leqslant\delta.$

Therefore, choosing $\delta=\varepsilon$, we get that $f$ is
$\varepsilon$-close to a polymorphism of $g$.

Finally, suppose that $m\geqslant 2$. If $f$ is a $\delta$-approximate
polymorphism of $g$ then the function $F\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$,
defined by $F((-1)^{x_{1}},\ldots,(-1)^{x_{n}})=(-1)^{f(x_{1},\ldots,x_{n})}$,
satisfies

$\operatorname*{\mathbb{E}}_{z\in\\{-1,1\\}^{nm}}\left[F\left((-1)^{b}\prod_{j=1}^{m}z_{1j},\ldots,(-1)^{b}\prod_{j=1}^{m}z_{nj}\right)\cdot(-1)^{b}\prod_{j=1}^{m}F(z_{1j},\ldots,z_{nj})\right]\geqslant
1-2\delta.$

Expanding the left-hand side according to the Fourier expansion of $F$, we
obtain

$\sum_{S_{0},\ldots,S_{m}\subseteq[n]}\hat{F}(S_{0})\cdots\hat{F}(S_{m})(-1)^{b(|S_{0}|+1)}\prod_{j=1}^{m}\operatorname*{\mathbb{E}}\left[\prod_{i\in
S_{0}\Delta
S_{j}}z_{ij}\right]=\sum_{S\subseteq[n]}(-1)^{b(|S|+1)}\hat{F}(S)^{m+1}.$

Since $\sum_{S}\hat{F}(S)^{2}=1$, we conclude that there must exist
$S\subseteq[n]$ such that $|\hat{F}(S)|^{m-1}\geqslant 1-2\delta$, which
implies that $|\hat{F}(S)|\geqslant 1-O(\delta)$, and so $f$ is
$O(\delta)$-close to $\bigoplus_{i\in S}x_{i}\oplus a$, for some
$a\in\\{0,1\\}$. We choose $\delta$ so the closeness guarantee becomes
$\varepsilon$.

To complete the proof, we need to show that
$b^{\oplus(|S|-1)}=a^{\oplus(m-1)}$. To this end, note that with probability
$1-O(\varepsilon)$ over $Z$,

$a\oplus\bigoplus_{i\in S}\left(\bigoplus_{j=1}^{m}Z_{ij}\oplus
b\right)=b\oplus\bigoplus_{j=1}^{m}\left(\bigoplus_{i\in S}Z_{ij}\oplus
a\right).$

Considering any $Z$ for which this holds, we immediately obtain $a\oplus
b^{\oplus|S|}=b\oplus a^{\oplus m}$, and so
$b^{\oplus(|S|-1)}=a^{\oplus(m-1)}$. ∎

###  3.1 Closeness to junta

In this section we complete the proof of Theorem 3.1 by proving Lemma 3.3. For
future use, we prove a more general version; the reader can mentally take
$f_{1}=\cdots=f_{m}=f$.

######  Lemma 3.7.

Fix a function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ which depends on all
coordinates, and assume moreover that $g$ is not of the form
$\bigoplus_{i=1}^{m}x_{i}\oplus b$.

For every $\varepsilon>0$ there exist $L\in\mathbb{N}$ and $\eta>0$ such that
if $f_{0},\ldots,f_{m}$ is an $\eta$-approximate multi-polymorphism of $g$
then $f_{j}$ is $\varepsilon$-close to an $L$-junta for some $j\in[m]$.

According to Lemma 3.2, we can reorder the coordinates of $g$ so that some
assignment $\alpha\in\\{0,1\\}^{m-1}$ satisfies

$g(\alpha_{1},\ldots,\alpha_{m-1},0)=g(\alpha_{1},\ldots,\alpha_{m-1},1).$

Since $g$ depends on all coordinates, we can find an assignment
$\beta\in\\{0,1\\}^{m-1}$ and $b\in\\{0,1\\}$ so that

$g(\beta_{1},\ldots,\beta_{m-1},x_{m})=x_{m}\oplus b.$

We will construct the junta by appealing to Jones’ regularity lemma (Theorem
2.9). First, we need to determine appropriate parameters:

  * •

Let $d,\tau,\delta$ be the parameters promised by Theorem 2.10 for
$p=2^{-(m-1)}$, $\varepsilon_{1}=\varepsilon/4$, and
$\varepsilon_{2}=\varepsilon^{m-1}/2$.

  * •

Let $L$ be the parameter promised by Theorem 2.9 for $d,\tau$ and
$\varepsilon/5$.

We will prove the lemma for $\eta=(\varepsilon/20)^{m}\delta$.

According to Theorem 2.9, we can find a set $T\subseteq[n]$ of at most $L$
coordinates such that

$\Pr_{z\in\\{0,1\\}^{T}}[\text{$(f_{m})_{T\to z}$ is
$(d,\tau)$-regular}]\geqslant 1-\varepsilon/5.$ (1)

We will show that this implies that either $f_{j}$ is $\varepsilon$-close to
constant for some $j\in[m-1]$, or

$\Pr_{z\in\\{0,1\\}^{T}}[\mathsf{var}((f_{m})_{T\to
z})\geqslant\varepsilon/4]\leqslant\varepsilon/4.$ (2)

This will complete the proof of Lemma 3.7. Indeed, if $f_{j}$ is
$\varepsilon$-close to constant for some $j\in[m-1]$ then the lemma clearly
hold. If (2) holds then define a $T$-junta $F$ by letting $F(x)$ be the
majority value of $(f_{m})_{T\to x|_{T}}$. We also think of $F$ as a function
$F_{T}\colon\\{0,1\\}^{T}\to\\{0,1\\}$. Since

$\mathsf{var}((f_{m})_{T\to z})=\Pr[(f_{m})_{T\to
z}=F_{T}(z)]\Pr[(f_{m})_{T\to z}\neq
F_{T}(z)]\geqslant\tfrac{1}{2}\Pr[(f_{m})_{T\to z}\neq F_{T}(z)],$

we see that

$\Pr[f_{m}\neq
F]=\operatorname*{\mathbb{E}}_{z\in\\{0,1\\}^{T}}\bigl{[}\Pr[(f_{m})_{T\to
z}\neq F_{T}(z)]\bigr{]}\leqslant
2\operatorname*{\mathbb{E}}_{z\in\\{0,1\\}^{T}}[\mathsf{var}((f_{m})_{T\to
z})]\stackrel{{\scriptstyle\eqref{eq:jones-conclusion-
ap}}}{{\leqslant}}2\left(\frac{\varepsilon}{4}\cdot
1+\left(1-\frac{\varepsilon}{4}\right)\cdot\frac{\varepsilon}{4}\right)\leqslant\varepsilon.$

In the rest of this section, we show that (1) implies that either $f_{j}$ is
$\varepsilon$-close to constant for some $j\in[m-1]$, or (2) holds. The proof
is by contradiction: we assume that (1) holds and $f_{j}$ is $\varepsilon$-far
from constant for all $j\in[m-1]$, and (2) fails, and reach a contradiction.

We construct a pair $(Z,W)$ of coupled $n\times m$ zero-one matrices in the
following way:

  * •

Choose $Z$ uniformly at random.

  * •

Let $R\subseteq\overline{T}$ consist of those rows $i\notin T$ such that
$\mathsf{row}_{i}(Z)|_{[m-1]}=\alpha$.

  * •

Define $W$ to be the matrix obtained from $Z$ by resampling $W_{im}$ for $i\in
R$.

By construction,

$(f_{0}\circ g^{n})(Z)=(f_{0}\circ g^{n})(W),$

and so

$\Pr_{Z,W}[(g\circ(f_{1},\ldots,f_{m}))(Z)\neq(g\circ(f_{1},\ldots,f_{m}))(W)]\leqslant
2\eta.$

In the rest of this section, we give a lower bound on the probability that
$(g\circ(f_{1},\ldots,f_{m}))(Z)\neq(g\circ(f_{1},\ldots,f_{m}))(W)$ which is
larger than $2\eta$, thus reaching a contradiction.

We will sample $Z,W$ in three stages:

  1. 1.

First, we sample the $m$ column of the rows in $T$.

  2. 2.

Second, we sample columns $1,\ldots,m-1$, which defines $R$, and column $m$ of
the rows in $\overline{T}\setminus R$.

  3. 3.

Third, we sample column $m$ of the rows in $R$. This is the only part in which
$Z,W$ differ.

We say that the first stage is successful if
$(f_{m})_{T\to\mathsf{col}_{m}(Z)|_{T}}$ has variance at least $\varepsilon/4$
and is $(d,\tau)$-regular. Our assumptions implies that this holds with
probability at least

$\varepsilon/4-\varepsilon/5=\varepsilon/20.$

Suppose now that the first stage is successful. We say that the second stage
is successful if (i) $f_{j}(\mathsf{col}_{j}(Z))=\beta_{j}$ for all
$j\in[m-1]$, and (ii)
$(f_{m})_{\overline{R}\to\mathsf{col}_{m}(Z)|_{\overline{R}}}$ has variance at
least $\delta$. Property (i) holds with probability at least
$\varepsilon^{m-1}$, since by assumption, $f_{j}$ is $\varepsilon$-far from
constant for all $j\in[m-1]$. Since each row in $\overline{T}$ belongs to $R$
with probability $2^{-(m-1)}$, by Theorem 2.10, property (ii) fails with
probability at most $\varepsilon^{m-1}/2$. Hence the first two stages are
successful with probability at least

$(\varepsilon/20)\cdot\varepsilon^{m-1}/2>(\varepsilon/20)^{m}.$

If the first two stages are successful then

$\displaystyle(g\circ(f_{1},\ldots,f_{m}))(Z)$
$\displaystyle=g(\beta_{1},\ldots,\beta_{m-1},f_{m}(\mathsf{col}_{m}(Z)))=f_{m}(\mathsf{col}_{m}(Z))\oplus
b,$ $\displaystyle(g\circ(f_{1},\ldots,f_{m}))(W)$
$\displaystyle=g(\beta_{1},\ldots,\beta_{m-1},f_{m}(\mathsf{col}_{m}(W)))=f_{m}(\mathsf{col}_{m}(W))\oplus
b,$

and $(f_{m})_{\overline{R}\to\mathsf{col}_{m}(Z)|_{\overline{R}}}$ has
variance at least $\delta$. Hence
$(g\circ(f_{1},\ldots,f_{m}))(Z)\neq(g\circ(f_{1},\ldots,f_{m}))(W)$ with
probability at least $2\delta$. Consequently,

$\Pr[(g\circ(f_{1},\ldots,f_{m}))(Z)\neq(g\circ(f_{1},\ldots,f_{m}))(W)]>2(\varepsilon/20)^{m}\delta\geqslant
2\eta,$

and we reach a contradiction.

##  4 Approximate multi-polymorphisms

In this section we prove the following generalization of Theorem 3.1.

######  Theorem 4.1.

Fix $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$, and let $p=\Pr[g=1]$. For every
$\varepsilon>0$ there exists $\delta>0$ (depending on both $g$ and
$\varepsilon$) such that if
$f_{0},\ldots,f_{m}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is a $\delta$-approximate
mult-polymorphism of $g$ then there exists an exact multi-polymorphism
$F_{0},\ldots,F_{m}$ of $g$ such that $f_{0}$ is $\varepsilon$-close to
$F_{0}$ with respect to $\mu_{p}$, and $f_{1},\ldots,f_{m}$ are
$\varepsilon$-close to $F_{1},\ldots,F_{m}$ with respect to $\mu_{1/2}$.

We will require an analog of Lemma 3.3, which we prove in Section 4.1.

######  Lemma 4.2.

Fix a function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ which depends on all
coordinates, and assume moreover that $g$ is not of the form
$\bigoplus_{i=1}^{m}x_{i}\oplus b$. Let $p=\operatorname*{\mathbb{E}}[g]$.

For every $\varepsilon>0$ there exist $L\in\mathbb{N}$ and $\eta>0$ such that
if $f_{0},\ldots,f_{m}$ is an $\eta$-approximate multi-polymorphism of $g$
then one of the following cases holds:

  1. (i)

There exists a set $T\subseteq[n]$ of at most $L$ coordinates such that
$f_{0}$ is $\varepsilon$-close to a $T$-junta with respect to $\mu_{p}$, and
$f_{1},\ldots,f_{m}$ are $\varepsilon$-close to $T$-juntas with respect to
$\mu_{1/2}$.

  2. (ii)

There exist $J\subseteq[m]$, $a\in\\{0,1\\}^{J}$ and $a_{0}\in\\{0,1\\}$ such
that $f_{0}$ is $\varepsilon$-close to $a_{0}$ with respect to $\mu_{p}$,
$f_{j}$ is $\varepsilon$-close to $a_{j}$ for all $j\in J$, and $g(x)=a_{0}$
whenever $x_{j}=a_{j}$ for all $j\in J$.

An argument analogous to Lemma 3.4 shows that it suffices to prove Theorem 4.1
when $g$ depends on all coordinates. The proof of Lemma 3.5 carries through,
as we briefly spell out.

######  Lemma 4.3.

Theorem 4.1 holds when $g$ depends on all coordinates and is not of the form
$\bigoplus_{i=1}^{m}x_{i}\oplus b$.

###### Proof.

Given $\varepsilon>0$, let $L\in\mathbb{N}$ and $\eta>0$ be the constants
promised by Lemma 4.2. We choose $\delta=\min(\varepsilon,\eta,2^{-mL}/3)$.

Apply Lemma 4.2 to the $\delta$-approximate multi-polymorphism
$f_{0},\ldots,f_{m}$ of $g$. In case (ii), there is nothing more to prove, so
assume that case (i) holds.

As in the proof of Lemma 3.5, we find restrictions
$F_{0},\ldots,F_{m}\colon\\{0,1\\}^{T}\to\\{0,1\\}$ which form a multi-
polymorphism of $g$, and such that $F_{j}$ is $\varepsilon$-close to $f_{j}$.
This completes the proof in this case. ∎

It remains to settle the case where $g$ is an XOR or an NXOR, in which case we
need to generalize slightly the argument of Lemma 3.6.

######  Lemma 4.4.

Theorem 4.1 holds when $g(x)=\bigoplus_{i=1}^{m}x_{i}\oplus b$.

###### Proof.

The proofs of the cases $m=0$ and $m=1$ are very similar to the corresponding
proofs in Lemma 3.6, so assume that $m\geqslant 2$. We will prove the lemma
for $\delta=c\varepsilon^{2}$, where $c>0$ is some constant.

Define functions $F_{0},\ldots,F_{m}\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ by
$F_{j}((-1)^{x_{1}},\ldots,(-1)^{x_{n}})=(-1)^{f_{j}(x_{1},\ldots,x_{n})}$. A
calculation along the lines of Lemma 3.6 shows that

$\sum_{S\subseteq[n]}(-1)^{b(|S|+1)}\prod_{j=0}^{m}\hat{F}_{j}(S)\geqslant
1-2\delta.$

We can bound the left-hand side in absolute value by

$\max_{S\subseteq[n]}|\hat{F}_{0}(S)|\sum_{S\subseteq[n]}\prod_{j=1}^{m}|\hat{F}_{j}(S)|.$

The generalized Hölder inequality shows that

$\sum_{S\subseteq[n]}\prod_{j=1}^{m}|\hat{F}_{j}(S)|\leqslant\sqrt[m]{\prod_{j=1}^{m}\sum_{S\subseteq[n]}|\hat{F}_{j}(S)|^{m}}\leqslant\sqrt[m]{\prod_{j=1}^{m}\sum_{S\subseteq[n]}|\hat{F}_{j}(S)|^{2}}\leqslant
1,$

and so $|\hat{F}_{0}(S)|\geqslant 1-2\delta$ for some $S\subseteq[n]$.
Parseval’s identity shows that $|\hat{F}_{0}(T)|^{2}=O(\delta)$ for all $T\neq
S$, and so

$\sum_{\begin{subarray}{c}T\subseteq[n]\\\ T\neq
S\end{subarray}}\prod_{j=0}^{m}|\hat{F}_{j}(T)|\leqslant
O(\sqrt{\delta})\cdot\sum_{T\subseteq[n]}\prod_{j=1}^{m}|\hat{F}_{j}(T)|=O(\sqrt{\delta}),$

implying that

$(-1)^{b(|S|+1)}\prod_{j=0}^{m}\hat{F}_{j}(S)\geqslant 1-O(\sqrt{\delta}).$

In particular, $|\hat{F}_{j}(S)|\geqslant 1-O(\sqrt{\delta})$ for all
$j\in\\{0,\ldots,m\\}$, and so each $f_{j}$ is $O(\sqrt{\delta})$-close to
$\bigoplus_{i\in S}x_{i}\oplus a_{j}$. We complete the proof by showing that
$a_{0}\oplus b^{\oplus(|S|-1)}=\bigoplus_{j=1}^{m}a_{j}$, using the same
argument that concludes Lemma 3.6. ∎

###  4.1 Closeness to junta

In this section we complete the proof of Theorem 4.1 by proving Lemma 4.2.

We break up the proof into four parts:

  1. 1.

Lemma 3.7 shows that _one_ of $f_{1},\ldots,f_{m}$ is close to a junta.

  2. 2.

This implies that $f_{0}$ is close to a junta (with respect to $\mu_{p}$).

  3. 3.

We conclude that _all_ of $f_{1},\ldots,f_{m}$ are close to juntas, unless
some of $f_{1},\ldots,f_{m}$ are close to constants.

  4. 4.

In the latter case, we show that $f_{0}$ is close to a constant $a_{0}$, and
those of $f_{1},\ldots,f_{m}$ which are close to constants constitute an
$a_{0}$-certificate for $g$.

We start by showing that $f_{0}$ is close to a junta.

######  Lemma 4.5.

Fix a function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ which depends on all
coordinates, and assume moreover that $g$ is not of the form
$\bigoplus_{i=1}^{m}x_{i}\oplus b$. Let $p=\operatorname*{\mathbb{E}}[g]$.

For every $\varepsilon>0$ there exist $L\in\mathbb{N}$ and $\eta>0$ such that
if $f_{0},\ldots,f_{m}$ is an $\eta$-approximate multi-polymorphism of $g$
then $f_{0}$ is $\varepsilon$-close to an $L$-junta with respect to $\mu_{p}$.

###### Proof.

Given $\varepsilon>0$, let $L,\eta_{0}$ be the parameters promised by Lemma
3.7, and let $\eta=\min(\eta_{0},\varepsilon)$. According to the lemma, there
exists $j\in[m]$ such that $f_{j}$ is $\varepsilon$-close to an $L$-junta.
Without loss of generality, suppose that $f_{m}$ is close to a $T$-junta,
where $T\subseteq[n]$ contains at most $L$ coordinates.

We construct a pair $(Z,W)$ of coupled $n\times m$ zero-one matrices as
follows: choose $Z$ uniformly at random, and let $W$ be the matrix obtained
from $Z$ by resampling $W_{im}$ for $i\notin T$.

With probability $1-2\varepsilon-2\eta=1-O(\varepsilon)$,

$(f_{0}\circ
g^{n})(Z)=(g\circ(f_{1},\ldots,f_{m}))(Z)=(g\circ(f_{1},\ldots,f_{m}))(W)=(f_{0}\circ
g^{n})(W).$

(In more detail, if $f_{m}$ is $\varepsilon$-close to the $T$-junta $F_{m}$,
then
$f_{m}(\mathsf{col}_{m}(Z))=F_{M}(\mathsf{col}_{m}(Z))=F_{M}(\mathsf{col}_{m}(W))=f_{m}(\mathsf{col}_{m}(W))$
with probability $1-2\varepsilon$.)

For each $x\in\\{0,1\\}^{T}$, define

$\varepsilon_{0}(x)=\Pr[(f_{0}\circ g^{n})(Z)\neq(f_{0}\circ g^{n})(W)\mid
g(\mathsf{row}_{i}(Z))=x_{i}\text{ for all }i\in T],$

so that
$\operatorname*{\mathbb{E}}_{\mu_{p}}[\varepsilon_{0}(x)]=O(\varepsilon)$.

Recall that for $i\notin T$, $\mathsf{row}_{i}(W)$ is obtained from
$\mathsf{row}_{i}(Z)$ by resampling the $m$th coordinate. Since $g$ depends on
the $m$th coordinate, the joint distribution of
$g(\mathsf{row}_{i}(Z)),g(\mathsf{row}_{i}(W))$ is $N_{\rho}^{\mu_{p}}$ for
some $\rho<1$. Therefore Lemma 2.12 shows that $(f_{0})_{T\to x}$ is
$O(\varepsilon_{0}(x))$-close to a constant function with respect to
$\mu_{p}$. In other words, $f_{0}$ is $O(\varepsilon)$-close to a $T$-junta
with respect to $\mu_{p}$. ∎

We now deduce that either one of $f_{1},\ldots,f_{m}$ is close to constant, or
all of $f_{1},\ldots,f_{m}$ are close to juntas.

######  Lemma 4.6.

Fix a function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$ which depends on all
coordinates, and assume moreover that $g$ is not of the form
$\bigoplus_{i=1}^{m}x_{i}\oplus b$. Let $p=\operatorname*{\mathbb{E}}[g]$.

For every $\varepsilon>0$ there exist $L\in\mathbb{N}$ and $\eta>0$ such that
if $f_{0},\ldots,f_{m}$ is an $\eta$-approximate multi-polymorphism of $g$
then there exists a set $T\subseteq[n]$ of at most $L$ coordinates such that
$f_{0}$ is $\varepsilon$-close to a $T$-junta with respect to $\mu_{p}$, and
furthermore one of the following cases holds:

  1. (i)

$f_{1},\ldots,f_{m}$ are $\varepsilon$-close to $T$-juntas.

  2. (ii)

One of $f_{1},\ldots,f_{m}$ is $\varepsilon$-close to a constant.

###### Proof.

Given $\varepsilon>0$, let $L,\eta_{0}$ be the parameters promised by Lemma
4.5 for $\varepsilon^{2m}$, and let $\eta=\min(\eta_{0},\varepsilon^{2m})$.
According to the lemma, $f_{0}$ is $\varepsilon^{2m}$-close to a $T$-junta,
where $T\subseteq[n]$ contains at most $L$ coordinates.

We can assume that all of $f_{1},\ldots,f_{m}$ are $\varepsilon$-far from
constants, since otherwise case (ii) holds. We will show that $f_{m}$ is
$O(\varepsilon^{2})$-close to a $T$-junta; an identical argument works for
$f_{1},\ldots,f_{m-1}$.

We construct a pair $(Z,W)$ of coupled $n\times m$ zero-one matrices: we
choose $Z$ uniformly at random, and let $W$ be the matrix obtained from $Z$ by
resampling the entire $i$th row for all $i\notin T$.

With probability $1-2\varepsilon^{2m}-2\eta=1-O(\varepsilon^{2m})$,

$(g\circ(f_{1},\ldots,f_{m}))(Z)=(f_{0}\circ g^{n})(Z)=(f_{0}\circ
g^{n})(W)=(g\circ(f_{1},\ldots,f_{m}))(W).$

Since $g$ depends on all coordinates, there exist $\beta\in\\{0,1\\}^{m-1}$
and $b\in\\{0,1\\}$ such that
$g(\beta_{1},\ldots,\beta_{m-1},x_{m})=x_{m}\oplus b$.

Let $j\in[m-1]$. Since $f_{j}$ is $\varepsilon$-far from constant,
$\Pr[f_{j}(\mathsf{col}_{j}(Z))=\beta_{j}]\geqslant\varepsilon$. We claim that
moreover,
$\Pr[f_{j}(\mathsf{col}_{j}(Z))=f_{j}(\mathsf{col}_{j}(W))=\beta_{j}]\geqslant\varepsilon^{2}$.
Indeed, for $x\in\\{0,1\\}^{T}$ define

$\varepsilon_{j}(x)=\Pr[f_{j}(\mathsf{col}_{j}(Z))=\beta_{j}\mid\mathsf{col}_{j}(Z)|_{T}=x].$

Then $\operatorname*{\mathbb{E}}[\varepsilon_{j}]\geqslant\varepsilon$, and

$\Pr[f_{j}(\mathsf{col}_{j}(Z))=f_{j}(\mathsf{col}_{j}(W))=\beta_{j}]=\operatorname*{\mathbb{E}}[\varepsilon_{j}^{2}]\geqslant\operatorname*{\mathbb{E}}[\varepsilon_{j}]^{2}=\varepsilon^{2}.$

It follows that with probability at least $\varepsilon^{2(m-1)}$, we have
$f_{j}(\mathsf{col}_{j}(Z))=f_{j}(\mathsf{col}_{j}(W))=\beta_{j}$ for all
$j\in[m-1]$. Denote this event by $E$. Thus

$\Pr[(g\circ(f_{1},\ldots,f_{m}))(Z)\neq(g\circ(f_{1},\ldots,f_{m}))(W)\mid
E]=\frac{O(\varepsilon^{2m})}{\varepsilon^{2(m-1)}}=O(\varepsilon^{2}).$

On the other hand, when $E$ happens,

$\displaystyle(g\circ(f_{1},\ldots,f_{m}))(Z)$
$\displaystyle=g(\beta_{1},\ldots,\beta_{m-1},f_{m}(\mathsf{col}_{m}(Z)))=f_{m}(\mathsf{col}_{m}(Z))\oplus
b,$ $\displaystyle(g\circ(f_{1},\ldots,f_{m}))(W)$
$\displaystyle=g(\beta_{1},\ldots,\beta_{m-1},f_{m}(\mathsf{col}_{m}(W)))=f_{m}(\mathsf{col}_{m}(W))\oplus
b,$

and so

$\Pr[f_{m}(\mathsf{col}_{m}(Z))\neq f_{m}(\mathsf{col}_{m}(W))\mid
E]=O(\varepsilon^{2}).$

Since $E$ only depends on the first $m-1$ columns, in fact

$\Pr[f_{m}(\mathsf{col}_{m}(Z))\neq
f_{m}(\mathsf{col}_{m}(W))]=O(\varepsilon^{2}).$

Finally, for $x\in\\{0,1\\}^{T}$ define

$\varepsilon_{m}(x)=\Pr[f_{m}(\mathsf{col}_{m}(Z))\neq
f_{m}(\mathsf{col}_{m}(W))\mid\mathsf{col}_{m}(Z^{\prime})|_{T}=x],$

so that $\operatorname*{\mathbb{E}}[\varepsilon_{m}]=O(\varepsilon^{2})$.
Since $\varepsilon_{m}=2\mathsf{var}(f_{m}|_{T\to x})$, we conclude that
$f_{m}$ is $O(\varepsilon^{2})$-close to a $T$-junta. ∎

We complete the proof of Lemma 4.2 by handling case (ii) of the preceding
lemma.

###### Proof of Lemma 4.2.

Given $\varepsilon>0$, let $L,\eta_{0}$ be the parameters promised by Lemma
4.6 for $\varepsilon^{m}$, and let $\eta=\min(\eta_{0},\varepsilon^{m})$.
Applying the lemma, we can assume that we are in case (ii). Without loss of
generality, suppose that $f_{m}$ is $\varepsilon^{m}$-close to a constant.

We construct a pair $(Z,W)$ of coupled $n\times m$ zero-one matrices as
follows: choose $Z$ uniformly at random, and let $W$ be the matrix obtained
from $Z$ by resampling the $m$th column.

With probability $1-2\varepsilon^{m}-2\eta=1-O(\varepsilon^{m})$,

$(f_{0}\circ
g^{n})(Z)=(g\circ(f_{1},\ldots,f_{m}))(Z)=(g\circ(f_{1},\ldots,f_{m}))(W)=(f_{0}\circ
g^{n})(W).$

Since $g$ depends on the $m$th coordinate, the joint distribution of the
inputs to $f_{0}$ on both sides is $N_{\rho}^{\mu_{p}}$ for some $\rho<1$.
Therefore Lemma 2.12 shows that $f_{0}$ is $O(\varepsilon^{m})$-close to a
constant $a_{0}$ with respect to $\mu_{p}$.

Let $J\subseteq[m]$ consist of the coordinates $j\in[m]$ such that $f_{j}$ is
$\varepsilon$-close to a constant $a_{j}$. Let $x\in\\{0,1\\}^{m}$ satisfy
$x_{j}=a_{j}$ for all $j\in J$. For each $j\notin J$, since $f_{j}$ is
$\varepsilon$-far from constant, $f_{j}(\mathsf{col}_{j}(Z))=x_{j}$ with
probability at least $\varepsilon$. For each $j\in J$, since $f_{j}$ is
$\varepsilon$-close to $a_{j}=x_{j}$, $f_{j}(\mathsf{col}_{j}(Z))=x_{j}$ with
probability at least $1-\varepsilon$. Hence with probability at least
$\varepsilon^{m-|J|}(1-\varepsilon)^{|J|}=\Omega(\varepsilon^{m-1})$,

$(g\circ(f_{1},\ldots,f_{m}))(Z)=g(x).$

On the other hand, with probability
$1-\varepsilon^{m}-\eta=1-O(\varepsilon^{m})$,

$(g\circ(f_{1},\ldots,f_{m}))(Z)=(f_{0}\circ g^{n})(Z)=a_{0}.$

Since $\Omega(\varepsilon^{m-1})>O(\varepsilon^{m})$, both events hold
simultaneously with positive probability, and so $g(x)=a_{0}$, as desired. ∎

##  5 List decoding regime

A polymorphism of $g$ is a function $f$ satisfying $f\circ g^{n}=g\circ
f^{m}$. There are two ways to relax this definition:

  * •

The 99% regime: study functions $f$ satisfying $f\circ g^{n}=g\circ f^{m}$ for
most inputs. Theorem 3.1 shows that such functions are close to exact
polymorphisms.

  * •

The 1% regime: study functions $f$ satisfying $f\circ g^{n}=g\circ f^{m}$ with
_significant_ probability. We would like to say that such functions are
_structured_.

When $g$ is the XOR function, the classic analysis of linearity testing
[BCH+96] shows that if $\Pr[f(x\oplus y)=f(x)\oplus f(y)]\geqslant
1/2+\varepsilon$, then $f$ is correlated with some character, that is, for
some $S\subseteq[n]$,

$\Pr\left[f(x)=\bigoplus_{i\in
S}x_{i}\right]\geqslant\frac{1}{2}+\varepsilon.$

Conversely, if $f$ is a random function then $\Pr[f(x\oplus y)=f(x)\oplus
f(y)]\approx 1/2$, showing that $1/2$ is the correct threshold for this kind
of structure.

What happens for other $g$? Let us take the AND function as a test case. If we
choose $f$ at random then $\Pr[f(x\land y)=f(x)\land f(y)]\approx 1/2$, and so
one could conjecture that when $\Pr[f(x\land y)=f(x)\land f(y)]\geqslant
1/2+\varepsilon$ then $f$ is correlated with some character. The Majority
function refutes this conjecture, since it satisfies $\Pr[f(x\land
y)=f(x)\land f(y)]\approx 3/4$ but is not correlated with any character.

The threshold $3/4$ is natural, since it corresponds to the following “almost-
random” construction: choose $f$ at random for inputs whose Hamming weight is
close to $n/2$ (where $n$ is the input size), and choose $f$ to be $0$
elsewhere. However, it is not the correct threshold: if we choose $f$ to be
Majority for inputs whose Hamming weight is close to $n/2$, and a _biased_
majority for other inputs, then $\Pr[f(x\land y)=f(x)\land f(y)]\approx
0.814975$.

Our main result shows that $0.814975$ is the correct threshold for AND: if
$\Pr[f(x\land y)=f(x)\land f(y)]\geqslant 0.814975+\varepsilon$ then $f$ is
correlated with some character. Moreover, we can guarantee that this character
has low degree.

The idea of the proof is to translate the question about Boolean variables to
a question on Gaussian space. To this end, we define a Gaussian analog of the
distribution $(g(x),x)$. It will be convenient to switch from $\\{0,1\\}$ to
$\\{-1,1\\}$.

######  Definition 5.1.

Let $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ be non-constant. The distribution
$\mathcal{N}_{g}$ is an $(m+1)$-variate Gaussian distribution
$(\mathcal{G}_{0},\mathcal{G}_{1},\ldots,\mathcal{G}_{m})$ given by:

  * •

Each coordinate is a standard Gaussian.

  * •

The Gaussians $\mathcal{G}_{1},\ldots,\mathcal{G}_{m}$ are independent.

  * •

For each $j\in[m]$,

$\operatorname*{\mathbb{E}}[\mathcal{G}_{0}\mathcal{G}_{j}]=\frac{\hat{g}(\\{j\\})}{\sqrt{1-\hat{g}(\emptyset)^{2}}}.$

Our main result states that if $\Pr[f\circ g^{n}=g\circ f^{m}]$ exceeds a
certain threshold, then $f$ is correlated with a low-degree character. The
result applies to any function other than XOR or NXOR; analogous results for
these functions (in which the character need not be low-degree) follow from a
generalization of the arguments in [BCH+96].

######  Definition 5.2.

Fix a function $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$. Let $s_{g}$ be the
infimum over all $s$ for which the following holds.

For every $\varepsilon>0$ there exist $\delta>0$ and $L\in\mathbb{N}$ such
that for all $n\in\mathbb{N}$, if $f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$
satisfies

$\Pr[f\circ g^{m}=g\circ f^{m}]\geqslant s+\varepsilon$

then $f$ has correlation at least $\delta$ with some character of degree at
most $L$, that is, there exists $S\subseteq[n]$, of size at most $L$, such
that

$\left|\operatorname*{\mathbb{E}}\left[f(x)\prod_{i\in
S}x_{i}\right]\right|\geqslant\delta.$

######  Theorem 5.3.

Fix a function $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ which depends on all
coordinates and is not $\pm\prod_{i=1}^{m}x_{i}$.

If $\operatorname*{\mathbb{E}}[g]\neq 0$ then let $s_{g}^{U}$ be the supremum
of

$\frac{1}{2}+\frac{1}{2}\operatorname*{\mathbb{E}}_{x\sim\mathcal{N}(0,1)^{n}}\left[\Bigl{|}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[g(q_{1}(\mathcal{G}_{1}),\ldots,q_{m}(\mathcal{G}_{m}))\mid\mathcal{G}_{0}=x]\Bigr{|}\right]$

over all $n\in\mathbb{N}$ and all functions
$q_{1},\ldots,q_{m}\colon\mathbb{R}^{n}\to\\{-1,1\\}$ satisfying
$\operatorname*{\mathbb{E}}[q_{1}]=\cdots=\operatorname*{\mathbb{E}}[q_{m}]=0$.

If $\operatorname*{\mathbb{E}}[g]=0$, instead let $s_{g}^{U}$ be the supremum
of

$\frac{1}{2}+\frac{1}{2}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[q_{0}(\mathcal{G}_{0})g(q_{1}(\mathcal{G}_{1}),\ldots,q_{m}(\mathcal{G}_{m}))]$

over all $n\in\mathbb{N}$ and all functions
$q_{0},\ldots,q_{m}\colon\mathbb{R}^{n}\to\\{-1,1\\}$ satisfying
$\operatorname*{\mathbb{E}}[q_{0}]=\cdots=\operatorname*{\mathbb{E}}[q_{m}]=0$.

Then $s_{g}\leqslant s_{g}^{U}$.

We can show that $s_{g}^{U}<1$ for all functions $g$ covered by the theorem.

######  Lemma 5.4.

If $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ depends on all coordinates and is not
$\pm\prod_{i=1}^{m}x_{i}$ then $s_{g}^{U}<1$.

If we take the supremum in Theorem 5.3 with the additional constraint that the
functions $q_{1},\ldots,q_{m}$ coincide, then the resulting value is a lower
bound on $s_{g}$.

######  Lemma 5.5.

Fix a function $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ which depends on all
coordinates and is not $\pm\prod_{i=1}^{m}x_{i}$.

If $\operatorname*{\mathbb{E}}[g]\neq 0$ then let $s_{g}^{L}$ be the supremum
of

$\frac{1}{2}+\frac{1}{2}\operatorname*{\mathbb{E}}_{x\sim\mathcal{N}(0,1)^{n}}\left[\Bigl{|}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[g(q(\mathcal{G}_{1}),\ldots,q(\mathcal{G}_{m}))\mid\mathcal{G}_{0}=x]\Bigr{|}\right]$

over all $n\in\mathbb{N}$ and all functions $q\colon\mathbb{R}^{n}\to[-1,1]$
satisfying $\operatorname*{\mathbb{E}}[q]=0$.

If $\operatorname*{\mathbb{E}}[g]=0$, instead let $s_{g}^{L}$ be the supremum
of

$\frac{1}{2}+\frac{1}{2}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[q(\mathcal{G}_{0})g(q(\mathcal{G}_{1}),\ldots,q(\mathcal{G}_{m}))]$

over all $n\in\mathbb{N}$ and all functions $q\colon\mathbb{R}^{n}\to[-1,1]$
satisfying $\operatorname*{\mathbb{E}}[q]=0$.

There exists a sequence of functions $f_{N}\colon\\{-1,1\\}^{N}\to\\{-1,1\\}$,
with $N\to\infty$, such that

$\Pr[f_{N}\circ g^{N}=g\circ f_{N}^{m}]\longrightarrow s^{L}_{g},$

and for each $\delta>0$ and $L\in\mathbb{N}$, for large enough $N$ the
functions $f_{N}$ do not have correlation at least $\delta$ with any character
of degree at most $L$.

Consequently, $s_{g}\geqslant s_{g}^{L}$.

We do not know whether $s_{g}^{U}>s_{g}^{L}$ holds for some $g$, that is,
whether there is any advantage in allowing $q_{1},\ldots,q_{m}$ to be
different.

When $\operatorname*{\mathbb{E}}[g]\neq 0$, for any function $q$ satisfying
$\operatorname*{\mathbb{E}}[q]=0$ we have

$\operatorname*{\mathbb{E}}_{x\sim\mathcal{N}(0,1)^{n}}\left[\Bigl{|}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[g(q(\mathcal{G}_{1}),\ldots,q(\mathcal{G}_{m}))\mid\mathcal{G}_{0}=x]\Bigr{|}\right]\geqslant\Bigl{|}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[g(q(\mathcal{G}_{1}),\ldots,q(\mathcal{G}_{m}))]\Bigr{|}=|\operatorname*{\mathbb{E}}[g]|,$

and so

$s_{g}^{L}\geqslant\frac{1}{2}+\frac{1}{2}|\operatorname*{\mathbb{E}}[g]|.$

This corresponds to the trivial construction in which $f$ is chosen randomly
around the middle slice, and
$\operatorname{\mathsf{sign}}(\operatorname*{\mathbb{E}}[g])$ elsewhere. The
following result, proved by taking $n=1$ and $q=\operatorname{\mathsf{sign}}$,
shows that we can improve it if all Fourier coefficients of $g$ on the first
level are non-zero.

######  Lemma 5.6.

If $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ satisfies
$\operatorname*{\mathbb{E}}[g]\neq 0$ and $\hat{g}(\\{x_{j}\\})\neq 0$ for all
$j\in[m]$ then
$s_{g}^{L}>\frac{1}{2}+\frac{1}{2}|\operatorname*{\mathbb{E}}[g]|$.

When $g$ is an AND function, we can show that $s_{g}^{U}$ is attained by $n=1$
and $q_{1}(x)=\cdots=q_{m}(x)=\operatorname{\mathsf{sign}}(x)$. In view of
Lemma 5.5, this gives an expression for $s_{g}$.

######  Theorem 5.7.

Let $m\geqslant 2$, and let $g(x_{1},\ldots,x_{m})=\min(x_{1},\ldots,x_{m})$.
Then

$s_{g}=\frac{1}{2}+\frac{1}{2}\operatorname*{\mathbb{E}}_{x\sim\mathcal{N}(0,1)}\left[\Bigl{|}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[g(\operatorname{\mathsf{sign}}(\mathcal{G}_{1}),\ldots,\operatorname{\mathsf{sign}}(\mathcal{G}_{m}))\mid\mathcal{G}_{0}=x]\Bigr{|}\right].$

In particular, when $m=2$, we obtain

$s_{\land}\approx 0.814975356673002,$

where $\land$ denotes the binary AND function $g(a,b)=a\land b=\min(a,b)$.

######  Remark 5.8.

If $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ is of the form
$\pm\prod_{i=1}^{m}x_{i}$ for $m\geqslant 2$ and $\Pr[f\circ g^{n}=g\circ
f^{m}]\geqslant\frac{1}{2}+\varepsilon$, then the proof of Lemma 3.6 shows
that $f$ has correlation $\Omega(\varepsilon^{1/(m-1)})$ with _some_
character. In contrast to Theorem 5.3, we cannot guarantee correlation with a
low-degree character.

###  5.1 Preliminaries

For $\lambda\in(-1,1)$ and (implicit) $n$, we denote by $\pi_{\lambda}$ the
product distribution on $\\{-1,1\\}^{n}$ in which each coordinate has
expectation $\lambda$ (this is the analog of the distributions $\mu_{p}$). We
denote the corresponding noise operator by $T_{\rho}^{\lambda}$; it multiplies
the $d$th level of the $\lambda$-biased Fourier expansion by $\rho^{d}$. If
$\lambda=0$ (corresponding to the uniform distribution) then we sometimes omit
the superscript.

We extend functions on $\\{-1,1\\}^{n}$ to functions on $\mathbb{R}^{n}$
multilinearly, that is, via the Fourier expansion (it doesn’t matter which
bias we use to define the Fourier expansion). The analog of
$T_{\rho}^{\lambda}$ in Gaussian space is $U_{\rho}^{\lambda}$.

The function $\operatorname{\mathsf{clip}}\colon\mathbb{R}\to[-1,1]$ clips its
argument to $[-1,1]$:

$\operatorname{\mathsf{clip}}(x)=\begin{cases}-1&\text{if }x<-1,\\\ x&\text{if
}-1\leqslant x\leqslant 1\\\ 1&\text{if }x>1.\end{cases}$

####  5.1.1 Invariance principle

Our proof will require a multidimensional version of the invariance principle
due to Mossel [Mos10].

######  Theorem 5.9.

Let $\mathcal{D}$ be an arbitrary distribution on $\\{-1,1\\}^{k}$, and let
$\mathcal{G}$ be a multivariate Gaussian distribution with the same mean
vector and covariance matrix. Denote the expectations of the individual
coordinates by $\mu_{1},\ldots,\mu_{k}$.

For every $\varepsilon,\gamma>0$ there exist $d\in\mathbb{N}$ and $\tau>0$
such that for any $f_{1},\ldots,f_{k}\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ and
$\gamma_{1},\ldots,\gamma_{k}\geqslant\gamma$, if
$\operatorname{Inf}_{i}^{\leqslant d}[f_{j}]\leqslant\tau$ for all $j\in[k]$
(where influence is with respect to $\pi_{\mu_{j}}$) and $i\in[n]$ then

$\left|\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}^{n}}[(T_{1-\gamma_{1}}^{\mu_{1}}f_{1})(x_{1})\cdots(T_{1-\gamma_{k}}^{\mu_{k}}f_{k})(x_{k})]-\operatorname*{\mathbb{E}}_{g\sim\mathcal{G}^{n}}[\operatorname{\mathsf{clip}}(T_{1-\gamma_{1}}^{\mu_{1}}f_{1})(g_{1})\cdots\operatorname{\mathsf{clip}}(T_{1-\gamma_{k}}^{\mu_{k}}f_{k})(g_{k})]\right|<\varepsilon.$

Furthermore, for each $j\in[k]$,

$|\operatorname*{\mathbb{E}}_{g\sim\mathcal{G}^{n}}[\operatorname{\mathsf{clip}}(T_{1-\gamma_{j}}^{\mu_{j}}f_{j})(g_{j})]-\operatorname*{\mathbb{E}}_{x\in\mathcal{D}^{n}}[f_{j}(x_{j})]|<\varepsilon.$

###### Proof.

[Mos10, Theorem 4.1] shows that for appropriate $d,\tau$ we have

$\left|\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}^{n}}[(T_{1-\gamma_{1}}^{\mu_{1}}f_{1})(x_{1})\cdots(T_{1-\gamma_{k}}^{\mu_{k}}f_{k})(x_{k})]-\operatorname*{\mathbb{E}}_{g\sim\mathcal{G}^{n}}[(T_{1-\gamma_{1}}^{\mu_{1}}f_{1})(g_{1})\cdots(T_{1-\gamma_{k}}^{\mu_{k}}f_{k})(g_{k})]\right|<\frac{\varepsilon}{2}.$

[Mos10, Theorem 4.2] shows that for appropriate $d,\tau$, for every $j\in[k]$
we have

$\left|\operatorname*{\mathbb{E}}_{g\sim\mathcal{G}^{n}}[((T_{1-\gamma_{j}}^{\mu_{j}}f_{j})(g_{j})-\operatorname{\mathsf{clip}}(T_{1-\gamma_{j}}^{\mu_{j}}f_{j})(g_{j}))^{2}]\right|<\left(\frac{\varepsilon}{2k}\right)^{2}.$

Applying Cauchy–Schwarz $k$ times implies that

$\left|\operatorname*{\mathbb{E}}_{g\sim\mathcal{G}^{n}}[(T_{1-\gamma_{1}}^{\mu_{1}}f_{1})(g_{1})\cdots(T_{1-\gamma_{k}}^{\mu_{k}}f_{k})(g_{k})]-\operatorname*{\mathbb{E}}_{g\sim\mathcal{G}^{n}}[\operatorname{\mathsf{clip}}(T_{1-\gamma_{1}}^{\mu_{1}}f_{1})(g_{1})\cdots\operatorname{\mathsf{clip}}(T_{1-\gamma_{k}}^{\mu_{k}}f_{k})(g_{k})]\right|<\frac{\varepsilon}{2},$

completing the proof of the main estimate.

The bound given by [Mos10, Theorem 4.2] also implies that for every $j\in[k]$,

$\left|\operatorname*{\mathbb{E}}_{g\sim\mathcal{G}^{n}}[\operatorname{\mathsf{clip}}(T_{1-\gamma_{j}}^{\mu_{j}}f_{j})(g_{j})]-\operatorname*{\mathbb{E}}_{g\in\mathcal{G}^{n}}[(T_{1-\gamma_{j}}^{\mu_{j}}f_{j})(g_{j})]\right|<\varepsilon.$

Since
$\operatorname*{\mathbb{E}}[(T_{1-\gamma_{j}}^{\mu_{j}}f_{j})(g_{j})]=\operatorname*{\mathbb{E}}[f_{j}(g_{j})]=\operatorname*{\mathbb{E}}[f_{j}(x_{j})]$,
this completes the proof. ∎

We will apply this theorem to the distribution $(g(x),x)$, whose Gaussian
analog we now calculate.

######  Lemma 5.10.

Let $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ be a non-constant function, and let
$\mu=\operatorname*{\mathbb{E}}[g]$. If $x$ is distributed uniformly over
$\\{-1,1\\}^{m}$ then the vector

$\frac{g(x)-\mu}{\sqrt{1-\mu^{2}}},x_{1},\ldots,x_{m}$

has the same mean vector and covariance matrix as $\mathcal{N}_{g}$.

###### Proof.

By construction, each coordinate has zero mean and unit variance, and the last
$m$ coordinates are independent. Hence it remains to compute the covariance
between the first coordinate and the $(j+1)$th coordinate, which corresponds
to $x_{j}$:

$\operatorname*{\mathbb{E}}_{x\in\\{-1,1\\}^{m}}\left[\frac{g(x)-\mu}{\sqrt{1-\mu^{2}}}x_{j}\right]=\frac{\hat{g}(\\{j\\})}{\sqrt{1-\mu^{2}}}.\qed$

####  5.1.2 Connected distributions

Theorem 5.9 requires adding noise to the function. We will do this in the
context of evaluating

$\operatorname*{\mathbb{E}}_{Z}[(f\circ g^{n})(Z)\cdot(g\circ f^{m})(Z)].$

In order to show that the noise only slightly changes this expression, we will
use a result of Mossel [Mos10] on connected distributions.

######  Definition 5.11 (Connected distribution).

Let $\mathcal{D}$ be a distribution on $\\{-1,1\\}^{k}$. For
$i\in\\{1,\ldots,k-1\\}$, let $G_{i}$ be the bipartite graph $(X,Y,E)$, where

  * •

$X$ is the projection of the support of $\mathcal{D}$ to the first $i$
coordinates.

  * •

$Y$ is the projection of the support of $\mathcal{D}$ to the last $k-i$
coordinates.

  * •

$(x,y)\in E$ if $(x,y)$ is in the support of $\mathcal{D}$.

The distribution $\mathcal{D}$ is _connected_ if all of $G_{1},\ldots,G_{k-1}$
are connected.

######  Theorem 5.12.

Fix a connected distribution $\mathcal{D}$ on $\\{-1,1\\}^{k}$ with mean
vector $\mu$. For every $\varepsilon>0$ there are
$\gamma_{1},\ldots,\gamma_{k}>0$ such that the following holds.

If $f_{1},\ldots,f_{k}\colon\\{-1,1\\}^{n}\to[-1,1]$ then

$\operatorname*{\mathbb{E}}_{x\sim\mathcal{D}^{n}}[f_{1}(x_{1})\cdots
f_{k}(x_{k})-(T_{1-\gamma_{1}}^{\mu_{1}}f_{1})(x_{1})\cdots(T_{1-\gamma_{k}}^{\mu_{k}}f_{k})(x_{k})]<\varepsilon.$

We prove this in Appendix B, using ideas from Mossel [Mos10].

We are interested in the distribution $(g(x),x)$. While this distribution is
not connected, we can show that unless $g$ is XOR or NXOR, we can rearrange it
so that it becomes connected.

######  Lemma 5.13.

Fix a function $g\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ which depends on all
coordinates and is not $\pm\prod_{i=1}^{m}x_{i}$.

After a suitable permutation, the distribution $(g(x),x)$ (where $x$ is chosen
uniformly from $\\{-1,1\\}^{m}$) is connected.

###### Proof.

By factoring the multilinear representation of $g$, we can uniquely decompose
$g$ as

$g(x)=g_{1}(x|_{S_{1}})\cdots g_{\ell}(x|_{S_{\ell}}),$

where $S_{1},\ldots,S_{\ell}$ form a decomposition of $[m]$, and none of
$g_{1},\ldots,g_{\ell}$ can be further decomposed in this way. Since $g$ is
not $\pm\prod_{i=1}^{m}x_{i}$, one of the sets, say $S_{1}$, contains at least
two points. We rearrange the inputs to $g$ so that $1,m\in S_{1}$. We will
prove that

$x_{1},x_{2},\ldots,x_{m-1},g(x),x_{m}$

is connected.

We will show that the graph $G_{i}$ is connected for $i\in[m-1]$; for $i=m$,
the same argument works, with $X$ and $Y$ switching roles.

Let $i\in[m-1]$. By construction, $X=\\{-1,1\\}^{i}$, and (up to permutation)
$Y$ is the collection of all $(y,b)\in\\{-1,1\\}^{(m-i)+1}$ such that
$g(x,y)=b$ for some $x\in X$. The edges are $(x,(y,g(x,y))$.

Since $g$ depends on all coordinates, there exists some $y\in\\{-1,1\\}^{m-i}$
such that $(y,1),(y,-1)\in Y$. Let $X_{-}=\\{x\in X:g(x,y)=-1\\}$ and
$X_{+}=\\{x\in X:g(x,y)=1\\}$; note that $X_{-},X_{+}\neq\emptyset$. We claim
that there exist $x_{-}\in X_{-}$, $x_{+}\in X_{+}$, and $(z,b)\in Y$ such
that $g(x_{-},z)=g(x_{+},z)$. Otherwise, for every $x_{-}\in X_{-}$ and
$x_{+}\in X_{+}$ we have $g(x_{-},z)g(x_{+},z)=-1$. This implies that $g(x,z)$
only depends on whether $x\in X_{+}$ or $x\in X_{-}$, and so we can write
$g(x,z)=g_{x}(x)g_{z}(z)$, which is impossible since $g_{x}$ depends on
$x_{1}$ and $g_{z}$ depends on $x_{m}$, and we assumed that $g_{1}(S_{1})$ is
indecomposable.

Recall $b=g(x_{-},z)=g(x_{+},z)$. The path

$(y,1)-x_{+}-(z,b)-x_{-}-(y,-1)$

shows that $(y,1)$ and $(y,-1)$ are connected.

If $(z,b)\in Y$ is arbitrary, let $x\in X$ be such that $g(x,z)=b$. Then
$(z,b)$ is connected to $(y,g(x,y))$ via $x$. Therefore all vertices in $Y$
are connected. Since every vertex in $X$ is connected to some vertex in $Y$,
we conclude that the entire graph is connected. ∎

####  5.1.3 Borell’s theorem

The upper bound in Lemma 5.4 derives from Borell’s isoperimetric theorem
[Bor85] in Gaussian space, in the following form.

######  Theorem 5.14.

Let $f\colon\mathbb{R}^{n}\to[-1,1]$ satisfy $\operatorname*{\mathbb{E}}[f]=0$
with respect to the standard Gaussian measure. For every $\rho\in[-1,1]$,

$\operatorname*{\mathbb{E}}[(U_{\rho}f)^{2}]\leqslant\frac{2}{\pi}\arcsin(\rho^{2}),$

which is tight for $f(x)=\operatorname{\mathsf{sign}}(x_{1})$.

The upper bound in Theorem 5.7 derives from a generalization of Borell’s
theorem due to Neeman [Nee14].

######  Theorem 5.15.

Let $f_{1},\ldots,f_{m}\colon\mathbb{R}^{n}\to\\{0,1\\}$ be arbitrary
functions. Let
$\mathcal{G}=(\mathcal{G}_{1},\ldots,\mathcal{G}_{m})\sim\mathcal{N}(\mu,\Sigma)^{n}$
be an $m$-dimensional multivariate Gaussian distribution, where all elements
of $\Sigma$ are non-negative.

Let $F_{1},\ldots,F_{m}\colon\mathbb{R}^{n}\to\\{0,1\\}$ be functions of the
form $F_{i}(x_{1},\ldots,x_{n})=1_{x_{1}\leqslant\theta_{i}}$, where
$\theta_{1},\ldots,\theta_{m}$ are chosen so that
$\operatorname*{\mathbb{E}}[F_{i}]=\operatorname*{\mathbb{E}}[f_{i}]$ for all
$i\in[m]$. Then

$\operatorname*{\mathbb{E}}[f_{1}(\mathcal{G}_{1})\cdots
f_{m}(\mathcal{G}_{m})]\leqslant\operatorname*{\mathbb{E}}[F_{1}(\mathcal{G}_{1})\cdots
F_{m}(\mathcal{G}_{m})].$

###  5.2 Proof of thm:list-decoding

We divide the proof into two parts. In the first part, we show that Theorem
5.3 holds when the functions $q_{0},\ldots,q_{m}$ in the definition of
$s_{g}^{U}$ are allowed to be $[-1,1]$-valued; we denote the resulting value
by $S_{g}^{U}$. We then show that the value of $s_{g}^{U}$ stays the same even
if we restrict $q_{0},\ldots,q_{m}$ to be $\\{-1,1\\}$-valued.

####  5.2.1 Proof for fractional functions

Let us first notice that if $\operatorname*{\mathbb{E}}[g]\neq 0$ then
$S_{g}^{U}$ is the supremum of

$\frac{1}{2}+\frac{1}{2}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[q_{0}(\mathcal{G}_{0})g(q_{1}(\mathcal{G}_{1}),\ldots,q_{m}(\mathcal{G}_{m}))]$

over all $n\in\mathbb{N}$ and all functions
$q_{0},q_{1},\ldots,q_{m}\colon\mathbb{R}^{n}\to[-1,1]$ satisfying
$\operatorname*{\mathbb{E}}[q_{1}]=\cdots=\operatorname*{\mathbb{E}}[q_{m}]=0$.
When $\operatorname*{\mathbb{E}}[g]=0$, we have defined $S_{g}^{U}$ using a
similar expression, with the additional constraint
$\operatorname*{\mathbb{E}}[q_{0}]=0$.

Let $\|\hat{g}\|_{1}=\sum_{S\subseteq[m]}|\hat{g}(S)|$, and set

$\varepsilon_{1}=\frac{\varepsilon}{3\|\hat{g}\|_{1}},\quad\varepsilon_{2}=\frac{\varepsilon}{(6m+3)\|\hat{g}\|_{1}},\quad\varepsilon_{3}=\frac{\varepsilon}{6m\|\hat{g}\|_{1}},\quad\varepsilon_{4}=\frac{\varepsilon}{m+1}.$

Let $\gamma_{0},\ldots,\gamma_{m}>0$ be the parameters given by Theorem 5.12
for $\varepsilon_{1}$. Let $d,\tau$ be the parameters given by Theorem 5.9 for
$\varepsilon_{2}$ and $\gamma=\min(\gamma_{0},\ldots,\gamma_{m})$. Let $L$ be
the parameter given by Theorem 2.9 for $d,\tau,\varepsilon_{4}$. Finally, we
define $\delta=2^{-L}\varepsilon_{3}$. We will assume that
$|\hat{f}(S)|\leqslant\delta$ for all $|S|\leqslant L$, and show that
$\Pr[f\circ g^{n}=g\circ f^{m}]\leqslant s^{U}_{g}+\varepsilon$.

According to Theorem 2.9, we can find a set $T$ of at most $L$ coordinates
such that with probability $1-\varepsilon_{4}$, $f_{T\to z}$ is
$(d,\tau)$-regular, and this holds both with respect to the uniform
probability and with respect to $\pi_{\operatorname*{\mathbb{E}}[g]}$. In
particular, if we choose $W\sim\\{-1,1\\}^{T\times m}$ then with probability
$1-(m+1)\varepsilon_{4}=1-\varepsilon$, the functions
$f_{j}=f_{T\to\mathsf{col}_{j}(W)}$ are $(d,\tau)$-regular with respect to
$\pi_{0}$ for all $j\in[m]$, and the function $f_{0}=f_{T\to g(W)}$ (where $g$
is applied row by row) is $(d,\tau)$-regular with respect to
$\pi_{\operatorname*{\mathbb{E}}[g]}$. If these properties are satisfied, we
say that $W$ is _good_.

For any $W$ and any $j\in[m]$, the expected value of $f_{j}$ is

$\sum_{S\subseteq T}\hat{f}(S)\prod_{i\in S}W_{ij},$

which is at most $2^{L}\delta=\varepsilon_{3}$ in absolute value.

Let $W$ be a good partial input, and denote by $\mathcal{D}(W)$ all inputs
compatible with $W$. Let
$q_{j}=\operatorname{\mathsf{clip}}(T_{1-\gamma_{j}}f_{j})$ for $j\in[m]$, and
let
$q_{0}(g)=\operatorname{\mathsf{clip}}(T_{1-\gamma_{j}}^{\operatorname*{\mathbb{E}}[g]}f_{0})(\sqrt{1-\operatorname*{\mathbb{E}}[g]^{2}}\cdot
g+\operatorname*{\mathbb{E}}[g])$ (we define $q_{0}$ so that if its input is a
standard Gaussian, then the input to $f_{0}$ has the same mean and variance as
$g(x)$). Combining Theorem 5.9 and Theorem 5.12 shows that for each
$S\subseteq[m]$,

$\left|\operatorname*{\mathbb{E}}_{Z\in\mathcal{D}(W)}\left[(f\circ
g^{n})(Z)\prod_{j\in
S}f_{j}(\mathsf{col}_{j}(Z))\right]-\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}\left[q_{0}(\mathcal{G}_{0})\prod_{j\in
S}q_{j}(\mathcal{G}_{j})\right]\right|\leqslant\varepsilon_{1}+\varepsilon_{2}.$

Theorem 5.9 also shows that for all $j\in[m]$,
$|\operatorname*{\mathbb{E}}[q_{j}]|\leqslant|\operatorname*{\mathbb{E}}[f_{j}]|+\varepsilon_{2}\leqslant\varepsilon_{2}+\varepsilon_{3}$.
Let

$q^{\prime}_{j}=\frac{q_{j}-\operatorname*{\mathbb{E}}[q_{j}]}{1+|\operatorname*{\mathbb{E}}[q_{j}]|},$

so that $\operatorname*{\mathbb{E}}[q^{\prime}_{j}]=0$. Then

$\left|\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}\left[q_{0}(\mathcal{G}_{0})\prod_{j\in
S}q_{j}(\mathcal{G}_{j})\right]-\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}\left[q_{0}(\mathcal{G}_{0})\prod_{j\in
S}\frac{q_{j}(\mathcal{G}_{j})}{1+|\operatorname*{\mathbb{E}}[q_{j}]|}\right]\right|\leqslant
1-\prod_{j\in S}\frac{1}{1+|\operatorname*{\mathbb{E}}[q_{j}]|}\leqslant
m(\varepsilon_{2}+\varepsilon_{3}),$

and

$\left|\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}\left[q_{0}(\mathcal{G}_{0})\prod_{j\in
S}\frac{q_{j}(\mathcal{G}_{j})}{1+|\operatorname*{\mathbb{E}}[q_{j}]|}\right]-\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}\left[q_{0}(\mathcal{G}_{0})\prod_{j\in
S}q^{\prime}_{j}(\mathcal{G}_{j})\right]\right|\leqslant\sum_{j\in
S}\frac{|\operatorname*{\mathbb{E}}[q_{j}]|}{1+|\operatorname*{\mathbb{E}}[q_{j}]|}\leqslant
m(\varepsilon_{2}+\varepsilon_{3}).$

Combining the three estimates, multiplying by $\hat{g}(S)$, and summing over
all $S\subseteq[m]$, we conclude that

$\left|\operatorname*{\mathbb{E}}_{Z\in\mathcal{D}(W)}[(f\circ
g^{n})(Z)(g\circ
f^{m})(Z)]-\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[q_{0}(\mathcal{G}_{0})g(q^{\prime}_{1}(\mathcal{G}_{1}),\ldots,q^{\prime}_{m}(\mathcal{G}_{m}))]\right|\leqslant\|\hat{g}\|_{1}(\varepsilon_{1}+(2m+1)\varepsilon_{2}+2m\varepsilon_{3})=\varepsilon.$

When $\operatorname*{\mathbb{E}}[g]=0$, we similarly replace $q_{0}$ with
$q^{\prime}_{0}$, adjusting $\varepsilon_{2},\varepsilon_{3}$ accordingly. We
conclude that

$\operatorname*{\mathbb{E}}_{Z\in\mathcal{D}(W)}[(f\circ g^{n})(Z)(g\circ
f^{m})(Z)]\leqslant(2S_{g}^{U}-1)+\varepsilon.$

Considering all possible $W$, this shows that

$\operatorname*{\mathbb{E}}_{Z}[(f\circ g^{n})(Z)(g\circ
f^{m})(Z)]\leqslant(2S_{g}^{U}-1)+2\varepsilon.$

It follows that

$\Pr[f\circ g^{n}=g\circ f^{m}]\leqslant S_{g}^{U}+\varepsilon.$

####  5.2.2 Rounding

Let $h(x_{0},\ldots,x_{m})=x_{0}g(x_{1},\ldots,x_{m})$, and note that $h$ is
multilinear.

To complete the proof of Theorem 5.3, we show that $S_{g}^{U}=s_{g}^{U}$.
Recall that $2S_{g}^{U}-1$ is the supremum of

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(q_{0}(\mathcal{G}_{0}),\ldots,q_{m}(\mathcal{G}_{m}))],$

where $n\in\mathbb{N}$ and $q_{0},\ldots,q_{m}\colon\mathbb{R}^{n}\to[-1,1]$
satisfy
$\operatorname*{\mathbb{E}}[q_{1}]=\cdots\operatorname*{\mathbb{E}}[q_{m}]=0$;
when $\operatorname*{\mathbb{E}}[g]=0$, we also require
$\operatorname*{\mathbb{E}}[q_{0}]=0$. In contrast, $2s_{g}^{U}-1$ is defined
similarly, with the functions $q_{0},\ldots,q_{m}$ being $\\{-1,1\\}$-valued.

For every $\varepsilon>0$ we can find $n\in\mathbb{N}$ and functions
$q_{0},\ldots,q_{m}\colon\mathbb{R}^{n}\to[-1,1]$ satisfying
$\operatorname*{\mathbb{E}}[q_{1}]=\cdots=\operatorname*{\mathbb{E}}[q_{m}]=0$
(and $\operatorname*{\mathbb{E}}[q_{0}]=0$ if
$\operatorname*{\mathbb{E}}[g]=0$), and furthermore

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(q_{0}(\mathcal{G}_{0}),\ldots,q_{m}(\mathcal{G}_{m}))]\geqslant
2S_{g}^{U}-1-\varepsilon.$

We will show that for every $\delta>0$, we can replace each $q_{i}$ by a
$\\{-1,1\\}$-valued function $Q_{i}$, with the same expectation as $q_{i}$,
such that

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(Q_{0}(\mathcal{G}_{0}),\ldots,Q_{m}(\mathcal{G}_{m}))]\geqslant
2S_{g}^{U}-1-\varepsilon-O(\delta).$

We replace the functions one by one. At step $i$, given
$Q_{0},\ldots,Q_{i-1},q_{i},\ldots,q_{m}$, we find a function $Q_{i}$ such
that

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(Q_{0}(\mathcal{G}_{0}),\ldots,Q_{i-1}(\mathcal{G}_{i-1}),Q_{i}(\mathcal{G}_{i}),q_{i+1}(\mathcal{G}_{i+1}),\ldots,q_{m}(\mathcal{G}_{m}))]\geqslant\\\
\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(Q_{0}(\mathcal{G}_{0}),\ldots,Q_{i-1}(\mathcal{G}_{i-1}),q_{i}(\mathcal{G}_{i}),q_{i+1}(\mathcal{G}_{i+1}),\ldots,q_{m}(\mathcal{G}_{m}))]-O(\delta).$

Since $q_{i}$ is bounded, we can discretize it to a function $\tilde{q}_{i}$
which attains finitely many values such that
$|q_{i}(x)-\tilde{q}_{i}(x)|\leqslant\delta$ for all $x\in\mathbb{R}$, and
furthermore
$\operatorname*{\mathbb{E}}[\tilde{q}_{i}]=\operatorname*{\mathbb{E}}[q_{i}]$.
One way to do so is to divide $[-1,1]$ into $2/\delta$ intervals of width
$\delta$, and for each such interval $I$, replace $q_{i}^{-1}(I)$ with its
expectation. Since $Q_{0},\ldots,Q_{i-1},q_{i+1},\ldots,q_{m}$ are all
bounded,

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(Q_{0}(\mathcal{G}_{0}),\ldots,Q_{i-1}(\mathcal{G}_{i-1}),\tilde{q}_{i}(\mathcal{G}_{i}),q_{i+1}(\mathcal{G}_{i+1}),\ldots,q_{m}(\mathcal{G}_{m}))]\geqslant\\\
\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(Q_{0}(\mathcal{G}_{0}),\ldots,Q_{i-1}(\mathcal{G}_{i-1}),q_{i}(\mathcal{G}_{i}),q_{i+1}(\mathcal{G}_{i+1}),\ldots,q_{m}(\mathcal{G}_{m}))]-O(\delta).$

The idea now is to find a distribution $\mathbf{Q}_{i}$ of $\\{-1,1\\}$-valued
functions such that
$\operatorname*{\mathbb{E}}[\mathbf{Q}_{i}(x)]=\tilde{q}_{i}(x)$ for all
$x\in\mathbb{R}$, and furthermore each distribution in the support of
$\mathbf{Q}_{i}$ has expectation $\operatorname*{\mathbb{E}}[q_{i}]$. Since
the function $h$ is multilinear,

$\operatorname*{\mathbb{E}}_{\mathbf{Q}_{i}}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(Q_{0}(\mathcal{G}_{0}),\ldots,Q_{i-1}(\mathcal{G}_{i-1}),\mathbf{Q}_{i}(\mathcal{G}_{i}),q_{i+1}(\mathcal{G}_{i+1}),\ldots,q_{m}(\mathcal{G}_{m}))]=\\\
\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[h(Q_{0}(\mathcal{G}_{0}),\ldots,Q_{i-1}(\mathcal{G}_{i-1}),\tilde{q}_{i}(\mathcal{G}_{i}),q_{i+1}(\mathcal{G}_{i+1}),\ldots,q_{m}(\mathcal{G}_{m}))]$

Therefore some function $Q_{i}$ in the support of $\mathbf{Q}_{i}$ satisfies
our requirements.

It remains to construct the distribution $\mathbf{Q}_{i}$. For each value $c$
in the support of $\tilde{q}_{i}$, consider $\tilde{q}_{i}^{-1}(c)$, and put
it in a measure-preserving bijection $\alpha$ with some interval $[0,1]$ (with
respect to an appropriately scaled Lebesgue measure). We round
$\tilde{q}_{i}^{-1}(c)$ as follows: choose $\theta\in[0,1]$ at random, give
$\alpha^{-1}([\theta,\theta+\frac{1+c}{2}])$ (wrapping if needed) the value
$+1$, and the rest of $\tilde{q}_{i}^{-1}(c)$ the value $-1$. This guarantees
the required properties.

###  5.3 Proof of lem:sg-ub

For $j\in[m]$, define

$\rho_{j}=\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[\mathcal{G}_{0}\mathcal{G}_{j}]=\frac{\hat{g}(\\{j\\})}{\sqrt{1-\operatorname*{\mathbb{E}}[g]^{2}}},$

and let

$a=\sqrt{\sum_{j=1}^{m}\rho_{j}^{2}}=\sqrt{\frac{\|g^{=1}\|^{2}}{\|g^{\geqslant
1}\|^{2}}}<1.$

Let $Z_{1},\ldots,Z_{m},W_{1},\ldots,W_{m}$ be independent standard Gaussians.
The vector

$\sum_{\begin{subarray}{c}i\in[m]\\\ \rho_{i}\neq
0\end{subarray}}\frac{\rho_{i}}{a}Z_{i},\quad
aZ_{1}+\sqrt{1-a^{2}}W_{1},\quad\ldots,\quad aZ_{m}+\sqrt{1-a^{2}}W_{m}$

has the same distribution as $\mathcal{N}_{g}$. Let us denote the first
coordinate by $Z_{0}$, which is some linear combination of
$Z_{1},\ldots,Z_{m}$.

We will bound $2s_{g}^{U}-1$. Suppose we are given
$q_{0},q_{1},\ldots,q_{m}\colon\mathbb{R}^{n}\to[-1,1]$ such that
$\operatorname*{\mathbb{E}}[q_{1}]=\cdots=\operatorname*{\mathbb{E}}[q_{m}]=0$.
For every $S\subseteq[m]$, we have

$\operatorname*{\mathbb{E}}\left[q_{0}(Z_{0})\prod_{i\in
S}q_{i}(aZ_{i}+\sqrt{1-a^{2}}W_{i})\right]=\operatorname*{\mathbb{E}}\left[q_{0}(Z_{0})\prod_{i\in
S}(U_{a}q_{i})(Z_{i})\right].$

Multiplying by $\hat{g}(S)$ and summing over all $S\subseteq[m]$, we obtain

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[q_{0}(\mathcal{G}_{0})g(q_{1}(\mathcal{G}_{1}),\ldots,q_{m}(\mathcal{G}_{m}))]=\operatorname*{\mathbb{E}}[q_{0}(Z_{0})g((U_{a}q_{1})(Z_{1}),\ldots,((U_{a}q_{m})(Z_{m})))]\leqslant\\\
\operatorname*{\mathbb{E}}[|g((U_{a}q_{1})(Z_{1}),\ldots,(U_{a}q_{m})(Z_{m}))|]\leqslant\sqrt{\operatorname*{\mathbb{E}}[g((U_{a}q_{1})(Z_{1}),\ldots,(U_{a}q_{m})(Z_{m}))^{2}]}.$

We proceed to bound the expression inside the square root:

$\operatorname*{\mathbb{E}}[g((U_{a}q_{1})(Z_{1}),\ldots,(U_{a}q_{m})(Z_{m}))^{2}]=\\\
\sum_{S_{1},S_{2}\subseteq[m]}\hat{g}(S_{1})\hat{g}(S_{2})\operatorname*{\mathbb{E}}\left[\prod_{i\in
S_{1}}(U_{a}q_{i})(Z_{i})\prod_{j\in
S_{2}}(U_{a}q_{j})(Z_{j})\right]=\sum_{S\subseteq[m]}\hat{g}(S)^{2}\prod_{i\in
S}\operatorname*{\mathbb{E}}[(U_{a}q_{i})^{2}],$

since
$\operatorname*{\mathbb{E}}[U_{a}q_{i}]=\operatorname*{\mathbb{E}}[q_{i}]=0$
for all $i\in[m]$. Applying Theorem 5.14, we conclude that

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[q_{0}(\mathcal{G}_{0})g(q_{1}(\mathcal{G}_{1}),\ldots,q_{m}(\mathcal{G}_{m}))]^{2}\leqslant\sum_{S\subseteq[m]}\hat{g}(S)^{2}\rho^{S},\text{
where
}\rho=\frac{2}{\pi}\arcsin(a^{2})=\frac{2}{\pi}\arcsin\frac{\|g^{=1}\|^{2}}{\|g^{\geqslant
1}\|^{2}}<1,$

and so

$s_{g}^{U}\leqslant\frac{1}{2}+\frac{1}{2}\sqrt{\langle
T_{\rho}g,g\rangle}<1.$

######  Remark 5.16.

We can generalize the proof technique by choosing $m$ parameters
$a_{1},\ldots,a_{m}$ rather than a single parameter $a$. The optimal
parameters can be found, in principle, using Lagrange multipliers. When $g$ is
symmetric, the optimal choice is $a_{1}=\cdots=a_{m}=a$.

###  5.4 Proof of lem:sg-lb

We will assume for simplicity that $s_{g}^{L}$ is achieved for some finite
$n$; the general case follows using very similar arguments. Also, we will
first assume that $q$ is $\\{-1,1\\}$-valued.

When $\operatorname*{\mathbb{E}}[g]\neq 0$, define
$q_{0}\colon\mathbb{R}^{n}\to\\{-1,1\\}$ by

$q_{0}(x)=\operatorname{\mathsf{sign}}\left(\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}^{n}}[g(q(\mathcal{G}_{1}),\ldots,q(\mathcal{G}_{m}))\mid\mathcal{G}_{0}=x]\right).$

We will consider functions on $Nn$ inputs, which we think of as composed of
$n$ vectors $x^{(1)},\ldots,x^{(n)}\in\\{-1,1\\}^{N}$. We lift the functions
$q,q_{0}$ from $\mathbb{R}^{n}$ to $\\{-1,1\\}^{Nn}$ by defining

$\tilde{q}(x^{(1)},\ldots,x^{(n)})=q\left(\frac{\sum_{i=1}^{N}x^{(1)}_{i}}{\sqrt{N}},\ldots,\frac{\sum_{i=1}^{N}x^{(n)}_{i}}{\sqrt{N}}\right),$

and similarly for $q_{0}$.

If $\operatorname*{\mathbb{E}}[g]=0$ then we define
$f_{Nn}\colon\\{-1,1\\}^{Nn}\to\\{-1,1\\}$ by $f_{Nn}=\tilde{q}$. Otherwise,
assume for definiteness that $\operatorname*{\mathbb{E}}[g]<0$, and define

$f_{Nn}(x^{(1)},\ldots,x^{(n)})=\begin{cases}\tilde{q}(x^{(1)},\ldots,x^{(n)})&\text{if
}\sum_{i=1}^{n}\sum_{j=1}^{N}x^{(i)}_{j}\geqslant\frac{\operatorname*{\mathbb{E}}[g]}{2}Nn,\\\
\tilde{q}_{0}(x^{(1)},\ldots,x^{(n)})&\text{if
}\sum_{i=1}^{n}\sum_{j=1}^{N}x^{(i)}_{j}<\frac{\operatorname*{\mathbb{E}}[g]}{2}Nn.\end{cases}$

The central limit theorem shows that $\Pr[f_{Nn}\circ g^{Nn}=g\circ
f_{Nn}^{m}]$ tends to $s_{g}^{L}$.

To complete the proof when $q$ is $\\{-1,1\\}$-valued, we need to show that
all low-degree Fourier coefficients of $f_{Nn}$ are small. The total weight of
all Fourier coefficients on the “$(L_{1},\ldots,L_{n})$ level” (containing
$L_{j}$ elements from $x^{(j)}$) tends to the corresponding Hermite
coefficient of $q$, and so each of these coefficients has magnitude

$\Theta\left(\frac{1}{\sqrt{\binom{N}{L_{1}}\cdots\binom{N}{L_{n}}}}\right)=\Theta\left(\frac{1}{N^{(L_{1}+\cdots+L_{n})/2}}\right).$

In particular, the degree $L$ Fourier coefficients have magnitude
$O(N^{-L/2})$.

Finally, if $q$ is not $\\{-1,1\\}$-valued, then we first construct fractional
($[-1,1]$-valued) functions $f^{*}_{Nn}$ with the desired properties. We then
convert them to Boolean functions $f_{Nn}$ by independently sampling
$f_{Nn}(x)$ for each $x\in\\{-1,1\\}^{Nn}$ according to the unique
distribution supported on $\\{-1,1\\}$ whose expectation is $f^{*}_{Nn}$.
Standard concentration bounds complete the proof.

###  5.5 Proof of lem:sg-nontrivial

For $x\in\mathbb{R}$, let

$\gamma(x)=\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[g(\operatorname{\mathsf{sign}}(\mathcal{G}_{1}),\ldots,\operatorname{\mathsf{sign}}(\mathcal{G}_{m}))\mid\mathcal{G}_{0}=x].$

In view of Lemma 5.5, it suffices to show that

$\operatorname*{\mathbb{E}}_{x\sim\mathcal{N}(0,1)}[|\gamma(x)|]>|\operatorname*{\mathbb{E}}[g]|.$

As observed in the introduction to Section 5, the triangle inequality shows
that

$\operatorname*{\mathbb{E}}_{x\sim\mathcal{N}(0,1)}[|\gamma(x)|]\geqslant\Bigl{|}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[g(\operatorname{\mathsf{sign}}(\mathcal{G}_{1}),\ldots,\operatorname{\mathsf{sign}}(\mathcal{G}_{m}))]\Bigr{|}=|\operatorname*{\mathbb{E}}[g]|,$

with equality only if $|\gamma(x)|=|\operatorname*{\mathbb{E}}[g]|$ almost
surely. Due to continuity, equality is only possible if
$\gamma(x)=\operatorname*{\mathbb{E}}[g]$ for all $x$.

When $x$ is very large in absolute value, it is very likely that
$\operatorname{\mathsf{sign}}(\mathcal{G}_{j})=\operatorname{\mathsf{sign}}(\rho_{j})\operatorname{\mathsf{sign}}(x)$,
where $\rho_{j}=\operatorname*{\mathbb{E}}[\mathcal{G}_{0}\mathcal{G}_{j}]\neq
0$ by assumption. Hence when $x$ is very large in absolute value, $\gamma(x)$
is close to a $g(y)$ for some $y\in\\{-1,1\\}^{m}$, and so $|\gamma(x)|\approx
1$. When $x$ is large enough, $|\gamma(x)|>|\operatorname*{\mathbb{E}}[g]|$.

###  5.6 Proof of thm:sg-AND

We will show that the supremum in the definition of $s_{g}^{U}$ in Theorem 5.3
is attained by $n=1$ and $q_{1}=\cdots=q_{m}$ being the sign of the first
coordinate. Lemma 5.5 gives a matching lower bound, showing that in this case,
$s_{g}=s_{g}^{U}$.

As shown in the proof of Theorem 5.3, $2s_{g}^{U}-1$ is the maximum of

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[q_{0}(\mathcal{G}_{0})g(q_{1}(\mathcal{G}_{1}),\ldots,q_{m}(\mathcal{G}_{m}))],$

and so it suffices to show that this expression is maximized when
$q_{1},\ldots,q_{m}$ are sign functions.

We will be using Theorem 5.15, and to this end we need to switch from
$\\{-1,1\\}$-valued functions to $\\{0,1\\}$-valued functions. Accordingly,
define $p_{i}(x)=(1+q_{i}(x))/2$, so that $q_{i}(x)=2p_{i}(x)-1$. We have

$g(q_{1},\ldots,q_{m})=2\prod_{i=1}^{m}\frac{1+q_{i}}{2}-1=2\prod_{i=1}^{m}p_{i}-1,$

and so $2s_{g}^{U}-1$ is the maximum of

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[(2p_{0}(\mathcal{G}_{0})-1)(2p_{1}(\mathcal{G}_{1})\cdots
p_{m}(\mathcal{G}_{m})-1)]=4\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[p_{0}(\mathcal{G}_{0})\cdots
p_{m}(\mathcal{G}_{m})]-2\operatorname*{\mathbb{E}}[p_{0}]+1.$

Incidentally, the formula for $g$ also shows that
$\hat{g}(\\{j\\})=2^{-(m-1)}$, and so
$\operatorname*{\mathbb{E}}[\mathcal{G}_{0}\mathcal{G}_{j}]>0$. Theorem 5.15
therefore shows that fixing $\operatorname*{\mathbb{E}}[p_{0}]$, the maximum
of the expression for $2s_{g}^{U}-1$ is attained when $p_{0},\ldots,p_{m}$ are
threshold functions of their first coordinate with the correct expectations.
In particular, $p_{1}(x)=\cdots=p_{m}(x)=1_{x_{1}\leqslant 0}$, and so
$q_{1}(x)=\cdots=q_{m}(x)=\operatorname{\mathsf{sign}}(x_{1})$. Maximizing
over $\operatorname*{\mathbb{E}}[p_{0}]$, we conclude that the supremum in the
definition of $s_{g}^{U}$ is attained for these $q_{1},\ldots,q_{m}$.

When $m=2$, this shows that

$s_{\land}=\frac{1}{2}+\frac{1}{2}\operatorname*{\mathbb{E}}_{x\in\mathcal{N}(0,1)}\left[\Bigl{|}\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[\operatorname{\mathsf{sign}}(\mathcal{G}_{1})\land\operatorname{\mathsf{sign}}(\mathcal{G}_{2})\mid\mathcal{G}_{0}=x]\Bigr{|}\right],$

where $a\land b=\min(a,b)$. To calculate this, note that given
$\mathcal{G}_{0}$, we can sample $\mathcal{G}_{1},\mathcal{G}_{2}$ by letting
$\mathcal{H}_{0},\mathcal{H}_{1},\mathcal{H}_{2}$ be independent standard
Gaussians and taking

$\mathcal{G}_{1}=\frac{\mathcal{G}_{0}+\mathcal{H}_{0}+\mathcal{H}_{1}}{\sqrt{3}},\quad\mathcal{G}_{2}=\frac{\mathcal{G}_{0}-\mathcal{H}_{0}+\mathcal{H}_{2}}{\sqrt{3}}.$

Denoting $\Phi^{c}(t)=\Pr[\mathcal{N}(0,1)>t]$, this shows that for
$x\in\mathbb{R}$,

$\operatorname*{\mathbb{E}}_{\mathcal{G}\sim\mathcal{N}_{g}}[\operatorname{\mathsf{sign}}(\mathcal{G}_{1})\land\operatorname{\mathsf{sign}}(\mathcal{G}_{2})\mid\mathcal{G}_{0}=x]=2\Pr[\mathcal{G}_{1},\mathcal{G}_{2}>0]-1=2\Pr[\mathcal{H}_{0}+\mathcal{H}_{1}>-x,-\mathcal{H}_{0}+\mathcal{H}_{2}>-x]-1=\\\
2\operatorname*{\mathbb{E}}_{y\sim\mathcal{N}(0,1)}[\Phi^{c}(-x-y)\Phi^{c}(-x+y)]-1.$

We conclude that

$s_{\land}=\frac{1}{2}+\frac{1}{2}\operatorname*{\mathbb{E}}_{x\sim\mathcal{N}(0,1)}\left|2\operatorname*{\mathbb{E}}_{y\sim\mathcal{N}(0,1)}[\Phi^{c}(-x-y)\Phi^{c}(-x+y)]-1\right|\approx
0.814975356673002.$

##  6 Exact classification

In this section we classify all exact multi-polymorphisms, that is, all exact
solutions to the equation $f_{0}\circ g^{n}=g\circ(f_{1},\ldots,f_{m})$, thus
proving Theorem 2.5. As mentioned in the introduction, this was essentially
solved by Dokow and Holzman [DH09]; they gave all solutions to the equation
when $f_{0},\ldots,f_{m}$ are _Paretian_ , that is, satisfy
$f_{j}(b,\ldots,b)=b$ for $b\in\\{0,1\\}$. When $g$ is not XOR or NXOR, they
gave all solutions under the relaxed assumption that $f_{0},\ldots,f_{m}$ are
_surjective_ , that is, non-constant.

We provide a new proof that of the characterization. Our proof goes one step
further and determines all solutions to the slightly more general equation

$f_{0}\circ g^{n}=h\circ(f_{1},\ldots,f_{m}),$

where $g,h\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ and
$f_{0},\ldots,f_{m}\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$. (We switched from
$\\{0,1\\}$ to $\\{-1,1\\}$ in the interest of symmetry.) In addition, we
complete the characterization when the functions $f_{0},\ldots,f_{m}$ are
allowed to be constant.

The argument is in two parts. In the first part, we classify (except to some
corner cases) all _real_ solutions to the equation above. That is, we allow
the functions to be real-valued rather than Boolean ($\\{-1,1\\}$-valued). We
extend a function $f\colon\\{-1,1\\}^{n}\to\mathbb{R}$ to a function on
$\mathbb{R}^{n}$ multilinearly. That is, we consider the Fourier expansion of
$f$,

$f(x)=\sum_{S\subseteq[n]}\hat{f}(S)\prod_{i\in S}x_{i},$

and extend $f$ to $\mathbb{R}^{n}$ using this expression.

Equivalently, we think of $f_{0},\ldots,f_{m},g,h$ as multilinear polynomials,
that is, polynomials in which no variable is squared, and interpret the
equation above in the following way:

$f_{0}(g(z_{11},\ldots,z_{1m}),\ldots,g(z_{n1},\ldots,z_{nm}))=h(f_{1}(z_{11},\ldots,z_{n1}),\ldots,f_{m}(z_{1m},\ldots,z_{nm})),$

which is an identity of multilinear polynomials.

In the second part, we determine which of these solutions correspond to
Boolean functions.

###  6.1 Multilinear classification

We use the notation $z_{IJ}$ to refer to the monomial $\prod_{i\in
I}\prod_{j\in J}z_{ij}$. We also use similar self-explanatory notations such
as $z_{iJ},z_{Ij}$. In case $I$ or $J$ are the empty set, $z_{IJ}$ represent
the constant monomial $1$.

Throughout, we assume that $f_{0},\ldots,f_{m}$ are multilinear polynomials
over the variables $x_{1},\ldots,x_{n}$; that $g,h$ are multilinear
polynomials over the variables $y_{1},\ldots,y_{m}$; and that

$f_{0}\circ g^{n}=h\circ(f_{1},\ldots,f_{m}).$

We first identify the set of coordinates that $f_{0},\ldots,f_{m}$ depend on.

######  Lemma 6.1.

Suppose that $f_{0},\ldots,f_{m}$ are non-constant, and that $g,h$ together
depend on all coordinates in $[m]$, where $m\geqslant 1$. Then $g,h$ depend on
the same coordinates, and either $\deg(g)=\deg(h)=1$, or the following holds.

There exists a set $U\subseteq[n]$ such that $f_{0},\ldots,f_{m}$ depend only
on the coordinates in $U$, and furthermore

$\hat{f}_{0}(U),\ldots,\hat{f}_{m}(U)\neq 0.$

If $|U|>1$ then moreover

$\hat{g}([m]),\hat{h}([m])\neq 0.$

###### Proof.

For $j\in[m]$, let $F_{i}=f_{i}-\hat{f}_{i}(\emptyset)$, and let
$H(y_{1},\ldots,y_{m})=h(y_{1}+\hat{f}_{1}(\emptyset),\ldots,y_{m}+\hat{f}_{m}(\emptyset))$.
Thus $H\circ(F_{1},\ldots,F_{m})=h\circ(f_{1},\ldots,f_{m})$. Similarly, let
$G=g-\hat{g}(\emptyset)$ and
$F_{0}(x_{1},\ldots,x_{n})=f_{0}(x_{1}+\hat{g}(\emptyset),\ldots,x_{n}+\hat{g}(\emptyset))$.
Thus $F_{0}\circ G^{n}=f_{0}\circ g^{n}$. Therefore

$F_{0}\circ G^{n}=H\circ(F_{1},\ldots,F_{m}),$ (3)

where
$\hat{F}_{1}(\emptyset)=\cdots=\hat{F}_{m}(\emptyset)=\hat{G}(\emptyset)=0$;
$F_{0},\ldots,F_{m}$ are non-constant; and $G,H$ together depend on all
coordinates in $[m]$. We will prove the lemma for the new functions
$F_{0},\ldots,F_{m},G,H$. By inspection, the lemma holds also for the original
functions.

Expanding (3) according to the Fourier expansion, and using the condition
$\hat{F}_{1}(\emptyset)=\cdots=\hat{F}_{m}(\emptyset)=\hat{G}(\emptyset)=0$,
we obtain

$\sum_{S\subseteq[n]}\hat{F}_{0}(S)\prod_{i\in S}\sum_{\emptyset\neq
T_{i}\subseteq[m]}\hat{G}(T_{i})\prod_{j\in
T_{i}}z_{ij}=\sum_{T\subseteq[m]}\hat{H}(T)\prod_{j\in T}\sum_{\emptyset\neq
S_{j}\subseteq[n]}\hat{F}_{j}(S_{j})\prod_{i\in S_{j}}z_{ij}.$ (4)

Notice that every monomial appears in exactly one summand on each side.

#####  $G$ depends on all coordinates

Let $T\neq\emptyset$ be such that $\hat{H}(T)\neq 0$. For every $j\in T$,
since $F_{j}$ is non-constant, $\hat{F}_{j}(S_{j})\neq 0$ for some
$S_{j}\neq\emptyset$. Comparing coefficients of $\prod_{j\in T}z_{S_{j}j}$ in
(4), we get

$\hat{F}_{0}(S)\prod_{i\in S}\hat{G}(T_{i})=\hat{H}(T)\prod_{j\in
T}\hat{F}_{j}(S_{j}),$

where $S=\bigcup_{j\in T}S_{j}$ and $T_{i}=\\{j\in T:i\in S_{j}\\}$. Thus
$\hat{F}_{0}(S)\neq 0$ and $\hat{G}(T_{i})\neq 0$ for all $i\in S$. For every
$j\in T$, since $S_{j}$ is non-empty, we can find $i\in S_{j}$, and so $j\in
T_{i}$. Consequently, if $H$ depends on some $j\in[m]$ then $G$ also depends
on $j$. This implies that $G$ depends on all coordinates.

#####  $H$ depends on all coordinates

Since $F_{0}$ is non-constant, $\hat{F}_{0}(S)\neq 0$ for some
$S\neq\emptyset$. Let $T\neq\emptyset$. Comparing coefficients of $z_{ST}$ in
(4), we get

$\hat{F}_{0}(S)\hat{G}(T)^{|S|}=\hat{H}(T)\prod_{j\in T}\hat{F}_{j}(S).$

Since $G$ depends on all coordinates, for every $j\in[m]$ there exists a set
$T$ containing $j$ such that $\hat{G}(T)\neq 0$. This shows that
$\hat{F}_{j}(S)\neq 0$ for all $j\in[m]$. We conclude that if $T\neq\emptyset$
then $\hat{G}(T)\neq 0$ iff $\hat{H}(T)\neq 0$. In particular, $G,H$ both
depend on all coordinates, and $\deg(G)=\deg(H)>1$.

This argument also shows that if $\hat{F}_{0}(S)\neq 0$ then
$\hat{F}_{j}(S)\neq 0$ for all $j\in[m]$.

##### There exists a unique inclusion-maximal set $U$ in the support of
$\hat{F}_{0}$

Let $U$ be an inclusion-maximal set in the support of the Fourier expansion of
$F_{0}$. Thus $\hat{F}_{0}(U),\hat{F}_{1}(U),\ldots,\hat{F}_{m}(U)\neq 0$. We
claim that $F_{0}$ depends only on the coordinates in $U$. Otherwise,
$\hat{F}_{0}(V)\neq 0$ for some $V\nsubseteq U$. Since $\deg(H)>1$, there
exists a set $T$ of size at least $2$ such that $\hat{H}(T)\neq 0$. Choose an
arbitrary $j\in T$. The coefficient of $z_{Uj}z_{V(T\setminus\\{j\\})}$ on the
right-hand side of (4) is

$\hat{H}(T)\hat{F}_{j}(U)\prod_{k\in T\setminus\\{j\\}}\hat{F}_{k}(V)\neq 0.$

The coefficient of the same monomial on the left-hand side of (4) is a
multiple of $\hat{F}_{0}(U\cup V)$, showing that $\hat{F}_{0}(U\cup V)\neq 0$,
which contradicts the choice of $U$.

#####  $F_{j}$ depends only on $U$

Let $j\in[m]$. We claim that $F_{j}$ also depends only on the coordinates in
$U$. Otherwise, $\hat{F}_{j}(V)\neq 0$ for some $V\nsubseteq U$. Since $H$
depends on all coordinates, there exists a set $T$ containing $j$ such that
$\hat{H}(T)\neq 0$. Comparing coefficients of
$z_{Vj}z_{U(T\setminus\\{j\\})}$, as before we obtain that either
$\hat{F}_{0}(V)\neq 0$ (if $|T|=1$) or $\hat{F}_{0}(V\cup U)\neq 0$ (if
$|T|>1$), which contradicts the fact that $F_{0}$ depends only on the
coordinates in $U$.

##### If $|U|>1$ then $\hat{G}([m]),\hat{H}([m])\neq 0$

We now show that if $|U|>1$ then the support of the Fourier expansion of $G$
is closed under union, and so $\hat{G}([m])\neq 0$ since $G$ depends on all
coordinates. This implies that $\hat{H}([m])\neq 0$ as well.

Let $i\in U$, and let $T_{1},T_{2}\neq\emptyset$ be two different sets in the
support of the Fourier expansion of $G$. The coefficient of
$z_{iT_{1}}z_{(U\setminus[i])T_{2}}$ on the left-hand side of (4) is

$\hat{F}_{0}(U)\hat{G}(T_{1})\hat{G}(T_{2})^{|U|-1}\neq 0.$

The coefficient of the same monomial on the right-hand side of (4) is a
multiple of $\hat{H}(T_{1}\cup T_{2})$, showing that $\hat{H}(T_{1}\cup
T_{2})\neq 0$ and so $\hat{G}(T_{1}\cup T_{2})\neq 0$. The support of the
Fourier expansion of $G$ is thus closed under union. ∎

We now determine a formula for all functions, except for some corner cases.

######  Lemma 6.2.

Suppose that $f_{0},\ldots,f_{m}$ are non-constant, that $g,h$ together depend
on all coordinates in $[m]$, where $m\geqslant 1$, and that
$\deg(g),\deg(h)>1$. Let $U$ be the set promised by Lemma 6.1, and suppose
that $|U|>1$.

There exist constants $A_{0},\ldots,A_{m},C,D\neq 0$ and
$\kappa_{0},\ldots,\kappa_{m},B_{0},\ldots,B_{m}$ such that

$\displaystyle g(y)$
$\displaystyle=C\prod_{j\in[m]}(y_{j}+\kappa_{j})-\kappa_{0},$ $\displaystyle
h(y)$ $\displaystyle=D\prod_{j\in[m]}(y_{j}+B_{j})-B_{0},$ $\displaystyle
f_{0}(x)$ $\displaystyle=A_{0}\prod_{i\in U}(x_{i}+\kappa_{0})-B_{0},$
$\displaystyle f_{j}(x)$ $\displaystyle=A_{j}\prod_{i\in
U}(x_{i}+\kappa_{j})-B_{j},$

where

$A_{0}C^{|U|}=D\prod_{j\in[m]}A_{j}.$

###### Proof.

Suppose for definiteness that $U=[n]$, where $n\geqslant 2$.

##### Reducing $g,f_{1},\ldots,f_{m}$ to affine shifts of monomials

Let $\kappa_{1},\ldots,\kappa_{m}$ be parameters to be chosen later. For
$j\in[m]$, define
$F_{j}(x_{1},\ldots,x_{n})=f_{j}(x_{1}-\kappa_{j},\ldots,x_{n}-\kappa_{j})$,
and let $G(y_{1},\ldots,y_{m})=g(y_{1}-\kappa_{1},\ldots,y_{m}-\kappa_{m})$.
Notice that

$f_{0}\circ G^{n}=h\circ(F_{1},\ldots,F_{m}),$

which implies that

$\sum_{S\subseteq[n]}\hat{f}_{0}(S)\prod_{i\in
S}\sum_{T_{i}\subseteq[m]}\hat{G}(T_{i})\prod_{j\in
T_{i}}z_{ij}=\sum_{T\subseteq[m]}\hat{h}(T)\prod_{j\in
T}\sum_{S_{j}\subseteq[n]}\hat{F}_{j}(S_{j})\prod_{i\in S_{j}}z_{ij}.$ (5)

We choose $\kappa_{j}$ in such a way that $\hat{F}_{j}([n-1])=0$. This is
possible since

$\hat{F}_{j}([n-1])=\hat{f}_{j}([n-1])-\kappa_{j}\hat{f}_{j}([n]),$

and by Lemma 6.1, $\hat{f}_{j}([n])\neq 0$. The lemma also implies that
$\hat{G}([m]),\hat{h}([m])\neq 0$.

Let $T\neq\emptyset,[m]$. Consider the monomial
$\zeta=z_{[n-1][m]}z_{nT}=z_{[n-1]\overline{T}}z_{[n]T}$. Since $\zeta$
mentions all row indices and all column indices, it only appears once on each
side of (5) (for $S=[n]$ and $T=[m]$). Comparing coefficients, we obtain

$\hat{f}_{0}([n])\hat{G}([m])^{n-1}\hat{G}(T)=\hat{h}([m])\prod_{j\in
T}\hat{F}_{j}([n])\prod_{j\notin T}\hat{F}_{j}([n-1])=0.$

It follows that $\hat{G}(T)=0$ for all $T\neq\emptyset,[m]$. Therefore there
exist constants $C\neq 0$ and $\kappa_{0}$ such that

$G(y_{1},\ldots,y_{m})=Cy_{[m]}-\kappa_{0}.$

Every monomial appearing on the left-hand side of (5) is thus of the form
$z_{S[m]}$ for some $S\subseteq[n]$.

Let $S_{1},\ldots,S_{m}\neq\emptyset$ be such that $\hat{F}_{j}(S_{j})\neq 0$.
The coefficient of $\prod_{j\in[m]}z_{S_{j}j}$ on the right-hand side of (5)
is

$\hat{h}([m])\prod_{j\in[m]}\hat{F}_{j}(S_{j})\neq 0,$

and so necessarily $S_{1}=\cdots=S_{m}$. Since we know that
$\hat{F}_{j}([n])\neq 0$ for all $j\in[m]$, it follows that the Fourier
expansions of $F_{1},\ldots,F_{m}$ are supported on $\emptyset,[n]$, and so
there exist $A_{1},\ldots,A_{m}\neq 0$ and $B_{1},\ldots,B_{m}$ such that

$F_{j}(x_{1},\ldots,x_{n})=A_{j}x_{[n]}-B_{j}.$

##### Reducing $f_{0},h$ to affine shifts of monomials

Let
$F_{0}(x_{1},\ldots,x_{n})=f_{0}(Cx_{1}-\kappa_{0},\ldots,Cx_{n}-\kappa_{0})$,
so that

$F_{0}\circ y_{[m]}^{n}=f_{0}\circ G^{n}.$

Similarly, let
$H(y_{1},\ldots,y_{m})=h(A_{1}y_{1}-B_{1},\ldots,A_{m}y_{m}-B_{m})$, so that

$H\circ(x_{[n]},\ldots,x_{[n]})=h\circ(F_{1},\ldots,F_{m}).$

Thus

$F_{0}(z_{1[m]},\ldots,z_{n[m]})=H(z_{[n]1},\ldots,z_{[n]m}).$

Every monomial appearing on the left-hand side is of the form $z_{S[m]}$, and
every monomial appearing on the right-hand side is of the form $z_{[n]T}$.
Consequently, the only monomials appearing in this equation are $1$ and
$z_{[n][m]}$. Therefore there exist $\alpha,\beta\neq 0$ and $\gamma,\delta$
such that

$\displaystyle F_{0}(x)$ $\displaystyle=\alpha x_{[n]}-\gamma,$ $\displaystyle
H(y)$ $\displaystyle=\beta y_{[m]}-\delta.$

Inspection shows that $\alpha=\beta$ (which correspond to $A_{0},D$) and
$\gamma=\delta$ (which correspond to $B_{0}$).

Unrolling, we get the formulas in the statement of the lemma. ∎

###  6.2 Boolean classification

Since we are mainly interested in Boolean functions, we need to determine when
functions of the form given by Lemma 6.2 are Boolean.

######  Lemma 6.3.

Suppose that $f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ is given by

$f=A\prod_{i=1}^{n}(x_{i}+\kappa_{i})-B,$

where $A\neq 0$ and $n\geqslant 1$. Then one of the following holds:

  * •

$\kappa_{1}=\cdots=\kappa_{n}=B=0$ and $A\in\\{-1,1\\}$, i.e.

$f=A\prod_{i=1}^{n}x_{i},\text{ where }A\in\\{-1,1\\}.$

  * •

$\kappa_{1},\ldots,\kappa_{n},B\in\\{-1,1\\}$ and
$A=2B/\prod_{i=1}^{n}(2\kappa_{i})$, i.e.

$f=2B\prod_{i=1}^{n}\frac{\kappa_{i}x_{i}+1}{2}-B,\text{ where
}\kappa_{1},\ldots,\kappa_{n},B\in\\{-1,1\\}.$

###### Proof.

If $n=1$ then $f\in\\{x_{1},-x_{1}\\}$. Now suppose that $n\geqslant 2$.
Choose an assignment $y_{i}\neq-\kappa_{i}$ for all $i\in[n]$, and let
$f(y)=F$, where $F+B\neq 0$. Let
$\rho_{i}=(\kappa_{i}-y_{i})/(\kappa_{i}+y_{i})$, and let $y_{S}$ be the point
different from $y$ on the indices in $S\subseteq[n]$. Then

$f(y_{S})=(F+B)\prod_{i\in S}\rho_{i}-B.$

Since $f(y_{S})\in\\{-1,1\\}$ for all $S$, the products $\prod_{i\in
S}\rho_{i}$ must attain exactly two different values. In particular,
considering singleton $S$, since $\rho_{i}\neq 1$ for all $i$, we deduce that
all $\rho_{i}$ are equal to some $\rho\neq 1$. If $\rho\neq 0$ then
$\rho^{2}\neq\rho$, hence $\rho^{2}=1$, implying that $\rho=-1$. Furthermore,
$-F=f(y_{\\{1\\}})=(F+B)\rho-B$, and so

$\rho=\frac{B-F}{B+F},\quad\kappa_{i}=\frac{1+\rho}{1-\rho}y_{i}=\frac{B}{F}y_{i}.$

If $\rho=-1$ then $B=0$ and so $\kappa_{1}=\cdots=\kappa_{m}=0$. If $\rho=0$
then $B=F$ and so $\kappa_{i}=y_{i}$. In both cases, we can compute $A$ via
$f(y)=F$. ∎

Putting everything together, we obtain our main classification.

######  Theorem 6.4.

Let $f_{0},\ldots,f_{m}\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$ and
$g,h\colon\\{-1,1\\}^{m}\to\\{-1,1\\}$ satisfy

$f_{0}\circ g^{n}=h\circ(f_{1},\ldots,f_{m}).$

Let $J\subseteq[m]$ consist of all $j$ such that $f_{j}$ is non-constant, and
let $H\colon\\{-1,1\\}^{J}\to\\{-1,1\\}$ be obtained from $h$ by fixing the
$\overline{J}$-coordinates to the constants $f_{j}$ for $j\in\overline{J}$.

One of the following holds:

  1. (i)

$f_{0}$ is constant, and $H=f_{0}$ is also constant.

  2. (ii)

$g$ and $H$ are constants, and $f_{0}(g,\ldots,g)=H$.

  3. (iii)

There exists $j\in J$ such that $g(y)=\gamma y_{j}$ and $H(y)=\eta y_{j}$, and
furthermore $f_{0}(\gamma x)=\eta f_{j}(x)$.

  4. (iv)

There exists $i\in[n]$ such that $f_{j}=\phi_{j}x_{i}$ for
$j\in\\{0,\ldots,m\\}$, and furthermore
$\phi_{0}g(y_{1},\ldots,y_{m})=H(\phi_{1}y_{1},\ldots,\phi_{m}y_{m})$.

  5. (v)

There exist non-empty sets $K\subseteq J$ and $U\subseteq[n]$ such that one of
the following holds:

    1. (a)

$g(y)=\gamma y_{K}$, $H(y)=\eta y_{K}$ and $f_{j}(x)=\phi_{j}x_{U}$ for $j\in
K\cup\\{0\\}$, where $\phi_{0}\gamma^{|U|}=\eta\prod_{j\in K}\phi_{j}$.

    2. (b)

There exist $\kappa_{j},B_{j}\in\\{-1,1\\}$ for $j\in K\cup\\{0\\}$ such that

$\displaystyle g(y)$ $\displaystyle=2\kappa_{0}\prod_{j\in
K}\frac{1+\kappa_{j}y_{j}}{2}-\kappa_{0},$ $\displaystyle H(y)$
$\displaystyle=2B_{0}\prod_{j\in K}\frac{1+B_{j}y_{j}}{2}-B_{0},$
$\displaystyle f_{0}(x)$ $\displaystyle=2B_{0}\prod_{i\in
U}\frac{1+\kappa_{0}x_{i}}{2}-B_{0},$ $\displaystyle f_{j}(x)$
$\displaystyle=2B_{j}\prod_{i\in U}\frac{1+\kappa_{j}x_{i}}{2}-B_{j}.$

###### Proof.

If $f_{0}$ is constant and $y\in\\{-1,1\\}^{J}$, then since the functions
$f_{j}$ are not constant for $j\in J$, we can find an input $z$ such that
$f_{0}=(h\circ(f_{1},\ldots,f_{m}))(z)=H(y)$, showing that $H$ is also
constant. This is case (i).

Now suppose that $f_{0}$ is not constant. We claim that $g$ depends only on
the coordinates in $J$. Otherwise, we can find two inputs $z^{(0)},z^{(1)}$,
differing only on the coordinates in $\overline{J}$, such that $g(z_{0})=0$
and $g(z_{1})=1$. Thus
$f_{0}(g(z^{(y_{1}})),\ldots,g(z^{(y_{n})}))=f_{0}(y_{1},\ldots,y_{n})$.
However, $f_{0}\circ g^{n}=h\circ(f_{1},\ldots,f_{m})$ is invariant to
changing only coordinates in $\overline{J}$, showing that $f_{0}$ is constant,
contradicting our assumption. From now on we think of $g$ as a function on
$\\{-1,1\\}^{J}$.

Let $K\subseteq J$ be the set of coordinates that $g,H$ together depend on.
According to Lemma 6.1, both of $g,H$ depends on all coordinates in $K$. If
$K=\emptyset$ then $g,H$ are both constants, which is case (ii). If
$K=\\{j\\}$ then $g,H$ are both of the form $\pm y_{j}$, which is case (iii).

If $|K|>1$ then $\deg(g),\deg(H)>1$, since a Boolean function of degree $1$
depends on a single coordinate. Therefore Lemma 6.1 shows that there exists a
non-empty set $U\subseteq[n]$ such that $f_{0},\ldots,f_{m}$ depends only on
the coordinates in $U$, and $\hat{f}_{0}(U),\ldots,\hat{f}_{m}(U)\neq 0$. If
$|U|=1$, say $U=\\{i\\}$, then each of $f_{0},\ldots,f_{m}$ is of the form
$\pm x_{i}$, which is case (iv). If $|U|>1$ then Lemma 6.2 shows that we are
in case (v): there exist constants $A_{j},C,D\neq 0$ and $\kappa_{j},B_{j}$
such that

$\displaystyle g(y)$ $\displaystyle=C\prod_{j\in
K}(y_{j}+\kappa_{j})-\kappa_{0},$ $\displaystyle H(y)$
$\displaystyle=D\prod_{j\in K}(y_{j}+B_{j})-B_{0},$ $\displaystyle f_{0}(x)$
$\displaystyle=A_{0}\prod_{i\in U}(x_{i}+\kappa_{0})-B_{0},$ $\displaystyle
f_{j}(x)$ $\displaystyle=A_{j}\prod_{i\in U}(x_{i}+\kappa_{j})-B_{j}.$

Lemma 6.3 applied to $f_{0},\ldots,f_{m}$ shows that for each $j\in
K\cup\\{0\\}$, either $\kappa_{j}=B_{j}=0$ or $\kappa_{j},B_{j}\in\\{-1,1\\}$.
Applying the same lemma to $g$ and $H$, we see that in fact either all
$\kappa_{j}$ and all $B_{j}$ equal $0$, or all of them belong to $\\{-1,1\\}$.
The former is subcase (va), and the latter is subcase (vb). ∎

Let us now switch back from $\\{-1,1\\}$ to $\\{0,1\\}$. We do so using the
correspondence

$0\leftrightarrow 1,\quad 1\leftrightarrow-1.$

Under this correspondence, product corresponds to XOR; the function

$2\prod_{i\in U}\frac{1+(-1)^{b_{i}}x_{i}}{2}-1$

corresponds to $\bigvee_{i\in U}(x_{i}\oplus b_{i})$; and the function

$-2\prod_{i\in U}\frac{1-(-1)^{b_{i}}x_{i}}{2}+1$

corresponds to $\bigwedge_{i\in U}(x_{i}\oplus b_{i})$.

Using this, we can translate Theorem 6.4 into $\\{0,1\\}$ variables, and
deduce Theorem 2.5 by taking $g=h$.

##  7 Open questions

Our work suggests many open questions. Here are some of them.

######  Open Question 1.

Can Theorem 3.1 be extended to polymorphisms of predicates? That is, given a
function $g\colon\\{0,1\\}^{m}\to\\{0,1\\}$, what we can say about functions
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ satisfying

$\Pr[(g\circ f^{m})(Z)=1\mid g(\mathsf{row}_{i}(Z))=1\text{ for all
}i\in[n]]\geqslant 1-\varepsilon?$

As mentioned in the introduction, Kalai [Kal02] proved a version of Theorem
3.1 for the predicate $\mathsf{NAE_{3}}$, and Friedgut and Regev proved a