# On sketching approximations for symmetric Boolean CSPs

Joanna Boyland Harvard College, Harvard University, Cambridge, MA, USA.
Emails: {jboyland,michaelhwang1,
<EMAIL_ADDRESS>Michael
Hwang11footnotemark: 1 Tarun Prasad11footnotemark: 1 Noah
Singer11footnotemark: 1 Supported by the Harvard College Research Program.
Santhoshini Velusamy School of Engineering and Applied Sciences, Harvard
University, Cambridge, MA, USA. Supported in part by a Google Ph.D.
Fellowship, a Simons Investigator Award to Madhu Sudan, and NSF Awards CCF
1715187 and CCF 2152413. Email<EMAIL_ADDRESS>
###### Abstract

A Boolean maximum constraint satisfaction problem, $\textsf{Max-CSP}(f)$, is
specified by a predicate $f:\\{-1,1\\}^{k}\to\\{0,1\\}$. An $n$-variable
instance of $\textsf{Max-CSP}(f)$ consists of a list of constraints, each of
which applies $f$ to $k$ distinct literals drawn from the $n$ variables. For
$k=2$, Chou, Golovnev, and Velusamy [CGV20] obtained explicit ratios
characterizing the $\sqrt{n}$-space _streaming_ approximability of every
predicate. For $k\geq 3$, Chou, Golovnev, Sudan, and Velusamy [CGSV21] proved
a general dichotomy theorem for $\sqrt{n}$-space _sketching_ algorithms: For
every $f$, there exists $\alpha(f)\in(0,1]$ such that for every $\epsilon>0$,
$\textsf{Max-CSP}(f)$ is $(\alpha(f)-\epsilon)$-approximable by an $O(\log
n)$-space _linear_ sketching algorithm, but
$(\alpha(f)+\epsilon)$-approximation sketching algorithms require
$\Omega(\sqrt{n})$ space.

In this work, we give closed-form expressions for the sketching approximation
ratios of multiple families of _symmetric_ Boolean functions. Letting
$\alpha^{\prime}_{k}=2^{-(k-1)}(1-k^{-2})^{(k-1)/2}$, we show that for odd
$k\geq 3$, $\alpha(k\textsf{AND})=\alpha^{\prime}_{k}$, and for even $k\geq
2$, $\alpha(k\textsf{AND})=2\alpha^{\prime}_{k+1}$. Thus, for every $k$,
$k\textsf{AND}$ can be $(2-o(1))2^{-k}$-approximated by $O(\log n)$-space
_sketching_ algorithms; we contrast this with a lower bound of Chou, Golovnev,
Sudan, Velingker, and Velusamy [CGS+22] implying that _streaming_
$(2+\epsilon)\cdot 2^{-k}$-approximations require $\Omega(n)$ space! We also
resolve the ratio for the “at-least-$(k-1)$-$1$’s” function for all even $k$;
the “exactly-$\frac{k+1}{2}$-$1$’s” function for odd $k\in\\{3,\ldots,51\\}$;
and fifteen other functions. We stress here that for general $f$, the
dichotomy theorem in [CGSV21] only implies that $\alpha(f)$ can be computed to
arbitrary precision in $\mathsf{PSPACE}$, and thus closed-form expressions
need not have existed _a priori_. Our analyses involve identifying and
exploiting structural “saddle-point” properties of this dichotomy.

Separately, for all _threshold_ functions, we give optimal “bias-based”
approximation algorithms generalizing [CGV20] while simplifying [CGSV21].
Finally, we investigate the $\sqrt{n}$-space _streaming_ lower bounds in
[CGSV21], and show that they are _incomplete_ for $3$AND, i.e., they fail to
rule out $(\alpha(\textsf{$3$AND})-\epsilon)$-approximations in $o(\sqrt{n})$
space.

##  1 Introduction

In this work, we consider the _streaming approximability_ of various _Boolean
constraint satisfaction problems_ , and we begin by defining these terms. See
[CGSV21, §1.1-2] for more details on the definitions.

###  1.1 Setup: The streaming approximability of Boolean CSPs

####  1.1.1 Boolean CSPs

Let $f:\\{-1,1\\}^{k}\to\\{0,1\\}$ be a Boolean function. In an $n$-variable
instance of the problem $\textsf{Max-CSP}(f)$, a _constraint_ is a pair
$C=(\mathbf{b},\mathbf{j})$, where $\mathbf{j}=(j_{1},\ldots,j_{k})\in[n]^{k}$
is a $k$-tuple of distinct _indices_ , and
$\mathbf{b}=(b_{1},\ldots,b_{k})\in\\{-1,1\\}^{k}$ is a _negation pattern_.

For Boolean vectors
$\mathbf{a}=(a_{1},\ldots,a_{n}),\mathbf{b}=(b_{1},\ldots,b_{n})\in\\{-1,1\\}^{n}$,
let $\mathbf{a}\odot\mathbf{b}$ denote their _coordinate-wise product_
$(a_{1}b_{1},\ldots,a_{n}b_{n})$. An _assignment_
$\bm{\sigma}=(\sigma_{1},\ldots,\sigma_{n})\in\\{-1,1\\}^{n}$ satisfies $C$
iff $f(\mathbf{b}\odot\bm{\sigma}|_{\mathbf{j}})=1$, where
$\bm{\sigma}|_{\mathbf{j}}$ is the $k$-tuple
$(\sigma_{j_{1}},\ldots,\sigma_{j_{k}})$ (i.e., $\bm{\sigma}$ satisfies $C$
iff $f(b_{1}\sigma_{j_{1}},\ldots,b_{k}\sigma_{j_{k}})=1$). An _instance_
$\Psi$ of $\textsf{Max-CSP}(f)$ consists of constraints $C_{1},\dots,C_{m}$
with non-negative weights $w_{1},\ldots,w_{m}$ where
$C_{i}=(\mathbf{j}(i),\mathbf{b}(i))$ and $w_{i}\in\mathbb{R}$ for each
$i\in[m]$; the _value_ $\textsf{val}_{\Psi}(\bm{\sigma})$ of an assignment
$\bm{\sigma}$ to $\Psi$ is the (weighted) fraction of constraints in $\Psi$
satisfied by $\bm{\sigma}$, i.e.,
$\textsf{val}_{\Psi}(\bm{\sigma})\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\tfrac{1}{W}\sum_{i\in[m]}w_{i}\cdot
f(\mathbf{b}(i)\odot\bm{\sigma}|_{\mathbf{j}(i)})$, where
$W=\sum_{i=1}^{m}w_{i}$. The _value_ $\textsf{val}_{\Psi}$ of an instance
$\Psi$ is the maximum value of any assignment $\bm{\sigma}\in\\{-1,1\\}^{n}$,
i.e., $\textsf{val}_{\Psi}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\max_{\bm{\sigma}\in\\{-1,1\\}^{n}}\textsf{val}_{\Psi}(\bm{\sigma})$.

####  1.1.2 Approximations to CSPs

For $\alpha\in[0,1]$, we consider the problem of _$\alpha$ -approximating
$\textsf{Max-CSP}(f)$_. In this problem, the goal of an algorithm
$\mathcal{A}$ is to, on input an instance $\Psi$, output an estimate
$\mathcal{A}(\Psi)$ such that with probability at least $\frac{2}{3}$,
$\alpha\cdot\textsf{val}_{\Psi}\leq\mathcal{A}(\Psi)\leq\textsf{val}_{\Psi}$.
For $\beta<\gamma\in[0,1]$, we also consider the closely related
$(\beta,\gamma)\textsf{-Max-CSP}(f)$. In this problem, the input instance
$\Psi$ is promised to either satisfy $\textsf{val}_{\Psi}\leq\beta$ or
$\textsf{val}_{\Psi}\geq\gamma$, and the goal is to decide which is the case
with probability at least $\frac{2}{3}$.

####  1.1.3 Streaming and sketching algorithms for CSPs

For various Boolean functions $f$, we consider algorithms which attempt to
approximate $\textsf{Max-CSP}(f)$ instances in the _(single-pass, insertion-
only) space- $s$ streaming setting_. Such algorithms can only use space $s$
(which is ideally small, such as $O(\log n)$, where $n$ is the number of
variables in an input instance), and, when given as input a CSP instance
$\Psi$, can only read the list of constraints in a single, left-to-right pass.

We also consider a (seemingly) weak class of streaming algorithms called
_sketching algorithms_ , where the algorithm’s output is determined by an
length-$s$ string called a “sketch” produced from the input stream, and the
sketch itself has the property that the sketch of the concatenation of two
streams can be computed from the sketches of the two component streams. (See
[CGSV21, §3.3] for a formal definition.) A special case of sketching
algorithms are _linear sketches_ , where each sketch (i.e., element of
$\\{0,1\\}^{s}$) encodes an element of a vector space and we perform vector
addition to combine two sketches.

###  1.2 Prior work and motivations

####  1.2.1 Prior results on streaming and sketching $\textsf{Max-CSP}(f)$

We first give a brief review of what is already known about the streaming and
sketching approximability of $\textsf{Max-CSP}(f)$. For
$f:\\{-1,1\\}^{k}\to\\{0,1\\}$, let
$\rho(f)\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\Pr_{\mathbf{b}\sim\mathsf{Unif}(\\{-1,1\\}^{k})}[f(\mathbf{b})=1]$,
where $\mathsf{Unif}(\\{-1,1\\}^{k})$ denotes the uniform distribution on
$\\{-1,1\\}^{k}$. For every $f$, the $\textsf{Max-CSP}(f)$ problem has a
trivial $\rho(f)$-approximation algorithm given by simply outputting $\rho(f)$
since
$\mathbb{E}_{\mathbf{a}\sim\mathsf{Unif}(\\{-1,1\\}^{n})}[\textsf{val}_{\Psi}(\mathbf{a})]=\Pr_{\mathbf{b}\sim\mathsf{Unif}(\\{-1,1\\}^{k})}[f(\mathbf{b})=1]=\rho(f)$.
We refer to a function $f$ as _approximation-resistant_ for some class of
algorithms (e.g., streaming or sketching algorithms with some space bound) if
it cannot be $(\rho(f)+\epsilon)$-approximated for any constant $\epsilon>0$.
Otherwise, we refer to $f$ as _approximable_ for the class of algorithms.

The first two CSPs whose $o(\sqrt{n})$-space streaming approximabilities were
resolved were Max-$2$XOR and Max-$2$AND. Kapralov, Khanna, and Sudan [KKS15]
showed that Max-$2$XOR is approximation-resistant to $o(\sqrt{n})$-space
streaming algorithms. Later, Chou, Golovnev, and Velusamy [CGV20], building on
earlier work of Guruswami, Velusamy, and Velingker [GVV17], gave an $O(\log
n)$-space linear sketching algorithm which
$(\frac{4}{9}-\epsilon)$-approximates Max-$2$AND for every $\epsilon>0$ and
showed that $(\frac{4}{9}+\epsilon)$-approximations require $\Omega(\sqrt{n})$
space, even for streaming algorithms.

In two recent works [CGSV21, CGSV21a], Chou, Golovnev, Sudan, and Velusamy
proved so-called _dichotomy theorems_ for sketching CSPs. In [CGSV21], they
prove the dichotomy for CSPs over the Boolean alphabet with negations of
variables (i.e., the setup we described in Section 1.1.1). In [CGSV21a], they
extend it to the more general case of CSPs over finite alphabets.111More
precisely, [CGSV21] and [CGSV21a] both consider the more general case of CSPs
defined by _families_ of functions of a specific arity. We do not need this
generality for the purposes of our paper, and therefore omit it.

[CGSV21] is most relevant for our purposes, as it concerns Boolean CSPs. For a
fixed constraint function $f:\\{-1,1\\}^{k}\to\\{0,1\\}$, the main result in
[CGSV21] is the following _dichotomy theorem_ : For any $0\leq\gamma<\beta\leq
1$, either

  1. 1.

$(\beta,\gamma)\textsf{-Max-CSP}(f)$ has an $O(\log n)$-space linear sketching
algorithm, _or_

  2. 2.

For all $\epsilon>0$, sketching algorithms for
$(\beta+\epsilon,\gamma-\epsilon)\textsf{-Max-CSP}(f)$ require
$\Omega(\sqrt{n})$ space.

Distinguishing whether (1) or (2) applies is equivalent to deciding whether
two convex polytopes (which depend on $f,\gamma,\beta$) intersect. We omit a
technical statement of this criterion, and instead focus on the following
corollary: there exists an $\alpha(f)\in[0,1]$ such that $\textsf{Max-CSP}(f)$
can be $(\alpha(f)-\epsilon)$-approximated by $O(\log n)$-space linear
sketches, but not $(\alpha(f)+\epsilon)$-approximated by $o(\sqrt{n})$-space
sketches, for all $\epsilon>0$; furthermore, $\alpha(f)$ equals the solution
to an explicit minimization problem, which we describe in Section 2.1 (in the
special case where $f$ is symmetric).

_A priori_ , it may be possible to achieve an
$(\alpha(f)+\epsilon)$-approximation with a $o(\sqrt{n})$-space _streaming_
algorithm. But [CGSV21] also extends the lower bound (case 2 of the dichotomy)
to cover streaming algorithms when special objects called _padded one-wise
pairs_ exist. See Section 2.4 below for a definition (again, specialized for
symmetric functions). The padded one-wise pair criterion is sufficient to
recover all previous streaming approximability results for Boolean functions
(i.e., [KKS15, CGV20]), and prove several new ones. In particular, [CGSV21]
proves that if $f:\\{-1,1\\}^{k}\to\\{0,1\\}$ has the property that there
exists $\mathcal{D}\in\Delta(f^{-1}(1))$ such that
$\mathop{\mathbb{E}}_{\mathbf{b}\sim\mathcal{D}}[b_{i}]=0$ for all $i\in[k]$
(where $[k]\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\\{1,\ldots,k\\}$), then $\textsf{Max-CSP}(f)$ is streaming
approximation-resistant. For symmetric Boolean CSPs, they also prove the
converse, and thus give a complete characterization for approximation
resistance [CGSV21, Lemma 2.14]. However, besides Max-$2$AND, [CGSV21] does
not explicitly analyze the approximation ratio of any CSP that is
“approximable”, i.e., not approximation resistant.

####  1.2.2 Questions from previous work

In this work, we address several major questions about streaming
approximations for Boolean CSPs which Chou, Golovnev, Sudan, and Velusamy
[CGSV21] leave unanswered:

  1. 1.

Can the framework in [CGSV21] be used to find closed-form sketching
approximability ratios $\alpha(f)$ for approximable problems $\textsf{Max-
CSP}(f)$ beyond Max-$2$AND?

  2. 2.

As observed in [CGS+22, §1.3], [CGSV21] implies the following “trivial upper
bound” on streaming approximability: for all $f$, $\alpha(f)\leq 2\rho(f)$.
How tight is this upper bound?

  3. 3.

Does the streaming lower bound (the “padded one-wise pair” criterion) in
[CGSV21] suffice to resolve the streaming approximability of every function?

  4. 4.

The optimal $(\alpha(f)-\epsilon)$-approximation algorithm for $\textsf{Max-
CSP}(f)$ in [CGSV21] requires running a “grid” of $O(1/\epsilon^{2})$
distinguishers for $(\beta,\gamma)\textsf{-Max-CSP}(f)$ distinguishing
problems in parallel. Can we obtain simpler optimal sketching approximations?

###  1.3 Our results

We study the questions in Section 1.2.2 for _symmetric_ Boolean CSPs.
Symmetric Boolean functions are those functions that depend only on the
Hamming weight of the input, i.e., number of $1$’s in the input.222Note that
the inputs are in $\\{-1,1\\}^{k}$; we define the Hamming weight as the number
of $1$’s, and not $-1$’s (which is arguably more “natural” under the mapping
$b\in\\{0,1\\}\mapsto(-1)^{b}\in\\{-1,1\\}$), for consistency with [CGSV21].
For a set $S\subseteq[k]$, we define $f_{S,k}:\\{-1,1\\}^{k}\to\\{0,1\\}$ as
the indicator function for the set
$\\{\mathbf{b}\in\\{-1,1\\}^{k}:\operatorname{wt}(\mathbf{b})\in S\\}$ (where
$\operatorname{wt}(\mathbf{b})$ denotes the Hamming weight of $\mathbf{b}$).
That is, $f_{S,k}(\mathbf{x})=1$ if and only if
$\operatorname{wt}(\mathbf{x})\in S$. Some well-studied examples of functions
in this class include $k\textsf{AND}=f_{\\{k\\},k}$, the _threshold functions_
$\mathsf{Th}^{i}_{k}=f_{\\{i,i+1,\ldots,k\\},k}$, and “exact weight” functions
$\mathsf{Ex}^{i}_{k}=f_{\\{i\\},k}$.333By [CGSV21, Lemma 2.14], if $S$
contains elements $s\leq\frac{k}{2}$ and $t\geq\frac{k}{2}$, not necessarily
distinct, then $f_{S,k}$ supports one-wise independence and is therefore
approximation-resistant (even to streaming algorithms). Thus, we focus on the
case where all elements of $S$ are either larger than or smaller than
$\frac{k}{2}$. Moreover, note that if $S^{\prime}=\\{k-s:s\in S\\}$, every
instance of $\textsf{Max-CSP}(f_{S,k})$ can be viewed as an instance of
$\textsf{Max-CSP}(f_{S^{\prime},k})$ with the same value, since for any
constraint $C=(\mathbf{b},\mathbf{j})$ and assignment
$\bm{\sigma}\in\\{-1,1\\}^{n}$, we have
$f_{S,k}(\mathbf{b}\odot\bm{\sigma}|_{\mathbf{j}})$ =
$f_{S^{\prime},k}(\mathbf{b}\odot(-\bm{\sigma})|_{\mathbf{j}})$. Thus, we
further narrow our focus to the case where every element of $S$ is larger than
$\frac{k}{2}$.

####  1.3.1 The sketching approximability of ${\textsf{Max-}}k\textsf{AND}$

Chou, Golovnev, and Velusamy [CGV20] showed that
$\alpha(\textsf{$2$AND})=\frac{4}{9}$ (and
$(\frac{4}{9}+\epsilon)$-approximation can be ruled out even for
$o(\sqrt{n})$-space streaming algorithms). For $k\geq 3$, while Chou,
Golovnev, Velusamy, and Sudan [CGSV21] give optimal sketching approximation
algorithms for $\textsf{Max-}k\textsf{AND}$, they do not explicitly analyze
the approximation ratio $\alpha(k\textsf{AND})$, and show only that it lies
between $2^{-k}$ and $2^{-(k-1)}$.

In this paper, we analyze the dichotomy theorem in [CGSV21], and obtain a
closed-form expression for the sketching approximability of
$\textsf{Max-}k\textsf{AND}$ for every $k$. For odd $k\geq 3$, define the
constant

$\alpha^{\prime}_{k}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\left(\frac{(k-1)(k+1)}{4k^{2}}\right)^{(k-1)/2}=2^{-(k-1)}\cdot\left(1-\frac{1}{k^{2}}\right)^{(k-1)/2}.$
(1.1)

In Section 4, we prove the following:

######  Theorem 1.2.

For odd $k\geq 3$, $\alpha(k\textsf{AND})=\alpha^{\prime}_{k}$, and for even
$k\geq 2$, $\alpha(k\textsf{AND})=2\alpha^{\prime}_{k+1}$.

Since $\rho(k\textsf{AND})=2^{-k}$, Theorem 1.2 also has the following
important corollary:

######  Corollary 1.3.

$\lim_{k\to\infty}\frac{\alpha(k\textsf{AND})}{2\rho(k\textsf{AND})}=1$.

Recall that [CGSV21] implies that $\alpha(f)\leq 2\rho(f)$ for all functions
$f$. Indeed, Chou, Golovnev, Sudan, Velusamy, and Velingker [CGS+22] show that
any function $f$ cannot be $(2\rho(f)+\epsilon)$-approximated even by
$o(n)$-space streaming algorithms. On the other hand, in Section 1.3.3 below,
we describe simple $O(\log n)$-space sketching algorithms for
$\textsf{Max-}k\textsf{AND}$ achieving the optimal ratio from [CGSV21]. Thus,
as $k\to\infty$, these algorithms achieve an asymptotically optimal
approximation ratio even among $o(n)$-space streaming algorithms!

####  1.3.2 The sketching approximability of other symmetric functions

We also analyze the sketching approximability of a number of other symmetric
Boolean functions. Specifically, for the threshold functions
$\mathsf{Th}^{k-1}_{k}$ for even $k$, we show that:

######  Theorem 1.4.

For even $k\geq 2$,
$\alpha(\mathsf{Th}^{k-1}_{k})=\frac{k}{2}\alpha^{\prime}_{k-1}$.

We prove Theorem 1.4 in Section 5.1 using techniques similar to our proof of
Theorem 1.2. We also provide partial results for $\mathsf{Ex}^{(k+1)/2}_{k}$,
including closed forms for small $k$ and an asymptotic analysis of
$\alpha(\mathsf{Ex}^{(k+1)/2}_{k})$:

######  Theorem 1.5 (Informal version of Theorem 5.11).

For odd $k\in\\{3,\ldots,51\\}$, there is an explicit expression for
$\alpha(\mathsf{Ex}^{(k+1)/2}_{k})$ as a function of $k$.

######  Theorem 1.6.

$\lim_{\text{odd
}k\to\infty}\frac{\alpha\left(\mathsf{Ex}^{(k+1)/2}_{k}\right)}{\rho\left(\mathsf{Ex}^{(k+1)/2}_{k}\right)}=1$.

We prove Theorems 1.5 and 1.6 in Section 5.2. Finally, in Section 5.3, we
explicitly resolve fifteen other cases (e.g., $f_{\\{2,3\\},3}$ and
$f_{\\{4\\},5}$) not covered by Theorems 1.2, 1.4 and 1.5.

####  1.3.3 Simple approximation algorithms for threshold functions

Chou, Golovnev, and Velusamy’s optimal $(\frac{4}{9}-\epsilon)$-approximation
for $2$AND [CGV20], like Guruswami, Velingker, and Velusamy’s earlier
$(\frac{2}{5}-\epsilon)$-approximation [GVV17], is based on measuring a
quantity called the _bias_ of an instance $\Psi$, denoted
$\textsf{bias}(\Psi)$, which is defined as follows: For each $i\in[n]$,
$\mathsf{diff}_{i}(\Psi)$ is the difference in total weight between
constraints where $x_{i}$ occurs positively and negatively, and
$\textsf{bias}(\Psi)\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\frac{1}{km}\sum_{i=1}^{n}|\mathsf{diff}_{i}(\Psi)|\in[0,1]$.444[GVV17,
CGV20] did not normalize by $\frac{1}{kW}$. In the sketching setting,
$\textsf{bias}(\Psi)$ can be estimated using standard $\ell_{1}$-norm
sketching algorithms [Ind06, KNW10].

In Section 7, we give simple optimal bias-based approximation algorithms for
threshold functions:

######  Theorem 1.7.

Let $f_{S,k}=\mathsf{Th}^{i}_{k}$ be a threshold function. Then for every
$\epsilon>0$, there exists a piecewise linear function $\gamma:[-1,1]\to[0,1]$
and a constant $\epsilon^{\prime}>0$ such that the following is a sketching
$(\alpha(f_{S,k})-\epsilon)$-approximation for $\textsf{Max-CSP}(f_{S,k})$: On
input $\Psi$, compute an estimate $\widehat{b}$ for $\textsf{bias}(\Psi)$ up
to a multiplicative $(1\pm\epsilon^{\prime})$ error and output
$\gamma(\widehat{b})$.

Our construction generalizes the algorithm in [CGV20] for $2$AND to all
threshold functions, and is also a simplification, since the [CGV20] algorithm
computes a more complicated function of $\widehat{b}$.

For all CSPs whose approximability we resolve in this paper, we apply an
analytical technique which we term the “max-min method;” see the discussion in
Section 2.3 below. For such CSPs, our algorithm can be extended to solve the
problem of outputting an approximately optimal _assignment_ (instead of just
the value of such an assignment). Indeed, for this problem, we give a simple
randomized streaming algorithm using $O(n)$ space and time:

######  Theorem 1.8 (Informal version of Theorem 7.7).

Let $f_{S,k}$ be a function for which the max-min method applies, such as
$k\textsf{AND}$, or $\mathsf{Th}^{k-1}_{k}$ (for even $k$). Then there exists
a constant $p^{*}\in[0,1]$ such that following algorithm, on input $\Psi$,
outputs an assignment with expected value at least
$\alpha(f_{S,k})\textsf{val}_{\Psi}$: Assign variable $i$ to $1$ if
$\mathsf{diff}_{i}(\Psi)\geq 0$ and $-1$ otherwise, and then flip each
variable’s assignment independently with probability $p^{*}$.

Our algorithm can potentially be derandomized using universal hash families,
as in Biswas and Raman’s recent derandomization [BR21] of the Max-$2$AND
algorithm in [CGV20].

####  1.3.4 Sketching vs. streaming approximability

Theorem 1.2 implies that $\alpha(\textsf{$3$AND})=\frac{2}{9}$. We prove that
the padded one-wise pair criterion of Chou, Golovnev, Sudan, and Velusamy
[CGSV21] is not sufficient to completely resolve the _streaming_
approximability of Max-$3$AND:

######  Theorem 1.9 (Informal version of Theorem 2.12 \+ 2.13).

The padded one-wise pair criterion in [CGSV21] does not rule out a
$o(\sqrt{n})$-space streaming $(\frac{2}{9}+\epsilon)$-approximation for
$3$AND for every $\epsilon>0$; however, it does rule out such an algorithm for
$\epsilon\gtrapprox 0.0141$.

We state these results formally in Section 2.4 and prove them in Section 6.
Separately, Theorem 1.4 implies that
$\alpha(\mathsf{Th}^{3}_{4})=\frac{4}{9}$, and the padded one-wise pair
criterion _can_ be used to show that $(\frac{4}{9}+\epsilon)$-approximating
$\textsf{Max-CSP}(\mathsf{Th}^{3}_{4})$ requires $\Omega(\sqrt{n})$ space in
the streaming setting (see 5.7 below).

###  1.4 Related work

The classical approximability of ${\textsf{Max-}}k\textsf{AND}$ has been the
subject of intense study, both in terms of algorithms [GW95, FG95, Zwi98,
Tre98, TSSW00, Has04, Has05, CMM09] and hardness-of-approximation [Hås01,
Tre98a, ST98, ST00, EH08, ST09], given its intimate connections to $k$-bit
PCPs. Charikar, Makarychev, and Makarychev [CMM09] constructed an
$\Omega(k2^{-k})$-approximation to ${\textsf{Max-}}k\textsf{AND}$, while
Samorodnitsky and Trevisan [ST09] showed that $k2^{-(k-1)}$-approximations and
$(k+1)2^{-k}$-approximations are $\mathbf{NP}$\- and UG-hard, respectively.

Interestingly, recalling that $\alpha(k\textsf{AND})\to
2\rho(k\textsf{AND})=2^{-(k-1)}$ as $k\to\infty$, in the large-$k$ limit our
simple randomized algorithm (given in Theorem 1.8) matches the performance of
Trevisan’s [Tre98] parallelizable LP-based algorithm for $k\textsf{AND}$,
which (to the best of our knowledge) was the first work on the general
$k\textsf{AND}$ problem! The subsequent works [Has04, Has05, CMM09]
superseding [Tre98] use more complex techniques involving semidefinite
programming, but are structurally similar to our algorithm in Theorem 1.8:
They all involve “guessing” an assignment $\mathbf{x}\in\mathbb{Z}_{2}^{n}$
and then perturbing each bit with constant probability.

##  2 Our techniques

In this section, we give a more detailed background on the technical aspects
of the dichotomy theorem in [CGSV21], and explain the novel aspects of our
analysis.

###  2.1 The Chou, Golovnev, Sudan, and Velusamy [CGSV21] framework for
symmetric functions

In this section, we describe the Chou, Golovnev, Sudan, and Velusamy [CGSV21]
framework for finding the optimal sketching approximation ratio of a symmetric
Boolean function $f_{S,k}$.

Let $\Delta(\\{-1,1\\}^{k})$ denote the space of all distributions on
$\\{-1,1\\}^{k}$. For a distribution $\mathcal{D}\in\Delta(\\{-1,1\\}^{k})$
and $\mathbf{x}\in\\{-1,1\\}^{k}$, we use $\mathcal{D}(\mathbf{x})$ to denote
the probability of sampling $\mathbf{x}$ in $\mathcal{D}$. To a distribution
$\mathcal{D}\in\Delta(\\{-1,1\\}^{k})$ we associate a _canonical instance_
$\Psi_{\mathcal{D}}$ of $\textsf{Max-CSP}(f_{S,k})$ on $k$ variables as
follows. Let $\mathbf{j}=(1,\ldots,k)$. For every negation pattern
$\mathbf{b}\in\\{-1,1\\}^{k}$, $\Psi_{\mathcal{D}}$ contains the constraint
$(\mathbf{b},\mathbf{j})$ with weight $\mathcal{D}(\mathbf{b})$.

We say a distribution $\mathcal{D}\in\Delta(\\{-1,1\\}^{k})$ is _symmetric_ if
all vectors of equal Hamming weight are equiprobable, i.e., for every
$\mathbf{x},\mathbf{y}\in\\{-1,1\\}^{k}$ such that
$\operatorname{wt}(\mathbf{x})=\operatorname{wt}(\mathbf{y})$,
$\mathcal{D}(\mathbf{x})=\mathcal{D}(\mathbf{y})$. Let
$\Delta_{k}\subseteq\Delta(\\{-1,1\\}^{k})$ denote the set of all symmetric
distributions on $\\{-1,1\\}^{k}$. Given $\mathcal{D}\in\Delta_{k}$, let
$\mathcal{D}\langle i\rangle\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\sum_{\mathbf{x}\in\\{-1,1\\}^{k}:\operatorname{wt}(\mathbf{x})=i}\mathcal{D}(\mathbf{x})$
denote the total probability mass on vectors of Hamming weight $i$. Note that
any vector $(\mathcal{D}\langle 0\rangle,\ldots,\mathcal{D}\langle k\rangle)$
of nonnegative values summing to $1$ uniquely determines a distribution
$\mathcal{D}\in\Delta_{k}$; we write $\mathcal{D}=(\mathcal{D}\langle
0\rangle,\ldots,\mathcal{D}\langle k\rangle)$ for notational convenience.

Let $\mathsf{Bern}(p)$ represent a random variable which is $1$ with
probability $p$ and $-1$ with probability $1-p$. For
$\mathcal{D}\in\Delta(\\{-1,1\\})^{k}$ and $p\in[0,1]$, let

$\lambda_{S}(\mathcal{D},p)\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathcal{D},\mathbf{b}\sim\mathsf{Bern}(p)^{k}}[f_{S,k}(\mathbf{a}\odot\mathbf{b})]=\mathop{\mathbb{E}}_{\mathbf{b}\sim\mathsf{Bern}(p)^{k}}[\textsf{val}_{\Psi_{\mathcal{D}}}(\mathbf{b})]$
(2.1)

denote the expected value of a “$p$-biased symmetric assignment” on
$\mathcal{D}$’s canonical instance. Also, for a symmetric distribution
$\mathcal{D}\in\Delta_{k}$, we define its (scalar) _marginal_

$\mu(\mathcal{D})\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\mathop{\mathbb{E}}_{\mathbf{b}\sim\mathcal{D}}[b_{1}]=\cdots=\mathop{\mathbb{E}}_{\mathbf{b}\sim\mathcal{D}}[b_{k}].$
(2.2)

In general, $\lambda_{S}$ is linear in $\mathcal{D}$ and degree-$k$ in $p$,
and $\mu$ is linear in $\mathcal{D}$. For $\mathcal{D}\in\Delta_{k}$, we
provide explicit formulas for $\lambda_{S}$ and $\mu$ in Section 3.

Roughly, [CGSV21] states that $\textsf{Max-CSP}(f_{S,k})$ is hard to
approximate in the sketching setting if there exist distributions
$\mathcal{D}_{N},\mathcal{D}_{Y}\in\Delta_{k}$ such that (1)
$\mu(\mathcal{D}_{N})=\mu(\mathcal{D}_{Y})$ and (2) $\mathcal{D}_{Y}$’s
canonical instance is highly satisfied by the trivial (all-ones) assignment
but (3) $\mathcal{D}_{N}$’s canonical instance is not well-satisfied by any
“biased symmetric assignment”. To be precise, for
$\mathcal{D}\in\Delta(\\{-1,1\\}^{k})$, let

$\beta_{S}(\mathcal{D})\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\sup_{p\in[0,1]}\lambda_{S}(\mathcal{D},p)\text{ and
}\gamma_{S}(\mathcal{D})\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\lambda_{S}(\mathcal{D},1),$ (2.3)

and define

$\alpha(f_{S,k})\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\inf_{\mathcal{D}_{N},\mathcal{D}_{Y}\in\Delta_{k}:~{}\mu(\mathcal{D}_{N})=\mu(\mathcal{D}_{Y})}\left(\frac{\beta_{S}(\mathcal{D}_{N})}{\gamma_{S}(\mathcal{D}_{Y})}\right).$
(2.4)

For every symmetric function $f_{S,k}$, [CGSV21] proves that $\alpha(f_{S,k})$
is the optimal sketching approximation ratio for $\textsf{Max-CSP}(f_{S,k})$:

######  Theorem 2.5 (Combines [CGSV21, Theorem 2.10 and Lemma 2.14]).

Let $f_{S,k}:\\{-1,1\\}^{k}\to\\{0,1\\}$ be a symmetric function. Then for
every $\epsilon>0$, there is an linear sketching
$(\alpha(f_{S,k})-\epsilon)$-approximation to $\textsf{Max-CSP}(f_{S,k})$ in
$O(\log n)$ space, but any sketching
$(\alpha(f_{S,k})+\epsilon)$-approximation to $\textsf{Max-CSP}(f_{S,k})$
requires $\Omega(\sqrt{n})$ space.

######  Remark.

In the general case where $f:\\{-1,1\\}^{k}\to\\{0,1\\}$ is not symmetric, the
approximability of $f$ is no longer characterized by Eq. 2.4. Instead,
[CGSV21] requires taking an infimum over _all_ (not necessarily symmetric)
distributions $\mathcal{D}_{N},\mathcal{D}_{Y}\in\Delta(\\{-1,1\\})^{k}$.
Moreover, a general distribution $\mathcal{D}\in\Delta(\\{-1,1\\})^{k}$ no
longer has a single scalar marginal (as in Eq. 2.2). Instead, we must consider
a _vector_ marginal $\bm{\mu}(\mathcal{D})=(\mu_{1},\ldots,\mu_{k})$ with
$i$-th component
$\mu_{i}=\mathop{\mathbb{E}}_{\mathbf{b}\sim\mathcal{D}}[b_{i}]$;
correspondingly, $\mathcal{D}_{N}$ and $\mathcal{D}_{Y}$ are required to
satisfy the constraint $\bm{\mu}(\mathcal{D}_{N})=\bm{\mu}(\mathcal{D}_{Y})$.
These issues motivate our focus on _symmetric_ functions in this paper. Since
we need to consider only symmetric distributions in Eq. 2.4, $\mathcal{D}_{Y}$
and $\mathcal{D}_{N}$ are each parameterized by $k+1$ variables (as opposed to
$2^{k}$ variables), and there is a single linear equality constraint (as
opposed to $k$ constraints).

###  2.2 Formulations of the optimization problem

In order to show that $\alpha(\textsf{$2$AND})=\frac{4}{9}$, Chou, Golovnev,
Sudan, and Velusamy [CGSV21, Example 1] use the following reformulation of the
optimization problem on the right hand side of Eq. 2.4. For a symmetric
function $f_{S,k}$ and $\mu\in[-1,1]$, let

$\beta_{S,k}(\mu)=\inf_{\mathcal{D}_{N}\in\Delta_{k}:~{}\mu(\mathcal{D}_{N})=\mu}\beta_{S}(\mathcal{D}_{N})\text{
and
}\gamma_{S,k}(\mu)=\sup_{\mathcal{D}_{Y}\in\Delta_{k}:~{}\mu(\mathcal{D}_{Y})=\mu}\gamma_{S}(\mathcal{D}_{Y});$
(2.6)

then

$\alpha(f_{S,k})=\inf_{\mu\in[-1,1]}\left(\frac{\beta_{S,k}(\mu)}{\gamma_{S,k}(\mu)}\right).$
(2.7)

The optimization problem on the right-hand side of Eq. 2.7 appears simpler
than that of Eq. 2.4 because it is univariate, but there is a hidden
difficulty: Finding an explicit solution requires giving explicit formulas for
$\beta_{S,k}(\mu)$ and $\gamma_{S,k}(\mu)$. In the case of
$\textsf{$2$AND}=f_{\\{2\\},2}$, Chou, Golovnev, Sudan, and Velusamy [CGSV21]
show that $\gamma_{\\{2\\},2}(\mu)$ is an explicit linear function of $\mu$;
maximize the quadratic $\lambda_{\\{2\\}}(\mathcal{D}_{N},p)$ over $p\in[0,1]$
to find $\beta_{\\{2\\}}(\mathcal{D}_{N})$; and then minimize
$\beta_{\\{2\\}}(\mathcal{D}_{N})$ given $\mu(\mathcal{D}_{N})=\mu$ to find
$\beta_{\\{2\\},2}(\mu)$. However, while for general symmetric functions
$f_{S,k}$ we can describe $\gamma_{S,k}(\mu)$ as an explicit piecewise linear
function of $\mu$ (see Lemma 3.3 below), we do not know how to find closed
forms for $\beta_{S,k}(\mu)$ even for $3$AND. Thus, in this work we introduce
a different formulation of the optimization problem:

$\alpha(f_{S,k})=\inf_{\mathcal{D}_{N}\in\Delta_{k}}\left(\frac{\beta_{S}(\mathcal{D}_{N})}{\gamma_{S,k}(\mu(\mathcal{D}_{N}))}\right).$
(2.8)

This reformulation is valid because

$\alpha(f_{S,k})=\inf_{\mu\in[-1,1],\mathcal{D}_{N}\in\Delta_{k}:~{}\mu(\mathcal{D}_{N})=\mu}\left(\frac{\beta_{S}(\mathcal{D}_{N})}{\gamma_{S,k}(\mu)}\right)=\inf_{\mathcal{D}_{N}\in\Delta_{k}}\left(\frac{\beta_{S}(\mathcal{D}_{N})}{\gamma_{S,k}(\mu(\mathcal{D}_{N}))}\right).$

We view optimizing directly over $\mathcal{D}_{N}\in\Delta_{k}$ as an
important conceptual switch. In particular, our formulation emphasizes the
calculation of $\beta_{S}(\mathcal{D}_{N})$ as the centrally difficult
feature, yet we can still take advantage of the relative simplicity of
calculating $\gamma_{S,k}(\mu)$.

###  2.3 Our contribution: The max-min method

_A priori_ , solving the optimization problem on the right-hand side of Eq.
2.8 still requires calculating $\beta_{S}(\mathcal{D}_{N})$, which involves
maximizing a degree-$k$ polynomial. To get around this difficulty, we have
made a key discovery, which was not noticed by Chou, Golovnev, Sudan, and
Velusamy [CGSV21] even in the $2$AND case. Let $\mathcal{D}_{N}^{*}$ minimize
the right-hand side of Eq. 2.8, and $p^{*}$ maximize
$\lambda_{S}(\mathcal{D}_{N}^{*},\cdot)$. After substituting
$\beta_{S}(\mathcal{D})=\sup_{p\in[0,1]}\lambda_{S}(\mathcal{D},p)$ in Eq.
2.8, and applying the max-min inequality, we get

$\displaystyle\alpha(f_{S,k})=\inf_{\mathcal{D}_{N}\in\Delta_{k}}\sup_{p\in[0,1]}\left(\frac{\lambda_{S}(\mathcal{D}_{N},p)}{\gamma_{S,k}(\mu(\mathcal{D}_{N}))}\right)$
$\displaystyle\geq\sup_{p\in[0,1]}\inf_{\mathcal{D}_{N}\in\Delta_{k}}\left(\frac{\lambda_{S}(\mathcal{D}_{N},p)}{\gamma_{S,k}(\mu(\mathcal{D}_{N}))}\right)$
(2.9)
$\displaystyle\geq\inf_{\mathcal{D}_{N}\in\Delta_{k}}\left(\frac{\lambda_{S}(\mathcal{D}_{N},p^{*})}{\gamma_{S,k}(\mu(\mathcal{D}_{N}))}\right)\,.$

Given $p^{*}$, the right-hand side of Eq. 2.9 is relatively easy to calculate,
being a ratio of a linear and piecewise linear function of $\mathcal{D}_{N}$.
Our discovery is that, in a wide variety of cases, the quantity on the right-
hand side of Eq. 2.9 _equals_ $\alpha(f_{S,k})$; that is,
$(\mathcal{D}_{N}^{*},p^{*})$ is a _saddle point_ of
$\frac{\lambda_{S}(\mathcal{D}_{N},p)}{\gamma_{S,k}(\mu(\mathcal{D}_{N}))}$.555This
term comes from the optimization literature; such points are also said to
satisfy the “strong max-min property” (see, e.g., [BV04, pp. 115, 238]). The
saddle-point property is guaranteed by von Neumann’s minimax theorem for
functions which are concave and convex in the first and second arguments,
respectively, but this theorem and the generalizations we are aware of do not
apply even to $3$AND.

This yields a novel technique, which we call the “max-min method”, for finding
a closed form for $\alpha(f_{S,k})$. First, we guess $\mathcal{D}_{N}^{*}$ and
$p^{*}$, and then, we show analytically that
$\frac{\lambda_{S}(\mathcal{D}_{N},p)}{\gamma_{S,k}(\mu(\mathcal{D}_{N}))}$
has a saddle point at $(\mathcal{D}_{N}^{*},p^{*})$ and that
$\lambda_{S}(\mathcal{D}_{N},p)$ is maximized at $p^{*}$. These imply that
$\frac{\lambda_{S}(\mathcal{D}_{N}^{*},p^{*})}{\gamma_{S,k}(\mu(\mathcal{D}_{N}^{*}))}$
is a lower and upper bound on $\alpha(f_{S,k})$, respectively. For instance,
in Section 4, in order to give a closed form for $\alpha(k\textsf{AND})$ for
odd $k$ (i.e., the odd case of Theorem 1.2), we guess
$\mathcal{D}_{N}^{*}\langle\frac{k+1}{2}\rangle=1$ and $p^{*}=\frac{k+1}{2k}$
(by using Mathematica for small cases), and then check the saddle-point and
maximization conditions in two separate lemmas (Lemmas 4.2 and 4.1,
respectively). Then, we show that $\alpha(k\textsf{AND})=\alpha^{\prime}_{k}$
by analyzing the right hand side of the appropriate instantiation of Eq. 2.9.
We use similar techniques for $k\textsf{AND}$ for even $k$ (also Theorem 1.2)
and for various other cases in Sections 5.3, 5.1 and 5.2.

In all of these cases, the $\mathcal{D}_{N}^{*}$ we construct is supported on
at most two distinct Hamming weights, which is the property which makes
finding $\mathcal{D}_{N}^{*}$ tractable (using computer assistance). However,
this technique is not a “silver bullet”: it is not the case that the sketching
approximability of every symmetric Boolean CSP can be exactly calculated by
finding the optimal $\mathcal{D}_{N}^{*}$ supported on two elements and using
the max-min method. Indeed, (as mentioned in Section 5.3) we verify using
computer assistance that this is not the case for $f_{\\{3\\},4}$.

Finally, we remark that the saddle-point property is precisely what defines
the value $p^{*}$ required for our simple classical algorithm for outputting
approximately optimal assignments for $\textsf{Max-CSP}(f_{S,k})$ where
$f_{S,k}=\mathsf{Th}^{i}_{k}$ is a threshold function (see Theorem 7.7).

###  2.4 Streaming lower bounds

Chou, Golovnev, Sudan, and Velusamy [CGSV21] also define the following
condition on pairs $(\mathcal{D}_{N},\mathcal{D}_{Y})$, stronger than
$\mu(\mathcal{D}_{N})=\mu(\mathcal{D}_{Y})$, which implies hardness of
${(\gamma,\beta)\textrm{-}\textsf{Max-CSP}(f)}$ for _streaming_ algorithms:

######  Definition 2.10 (Padded one-wise pairs, [CGSV21, §2.3] (symmetric
case)).

A pair of distributions $(\mathcal{D}_{Y},\mathcal{D}_{N})\in\Delta_{k}$ forms
a _padded one-wise pair_ if there exists $\tau\in[0,1]$ and distributions
$\mathcal{D}_{0},\mathcal{D}_{Y}^{\prime},\mathcal{D}_{N}^{\prime}\in\Delta_{k}$
such that (1) $\mu(\mathcal{D}_{Y}^{\prime})=\mu(\mathcal{D}_{N}^{\prime})=0$
and (2) $\mathcal{D}_{Y}=\tau\mathcal{D}_{0}+(1-\tau)\mathcal{D}^{\prime}_{Y}$
and $\mathcal{D}_{N}=\tau\mathcal{D}_{0}+(1-\tau)\mathcal{D}^{\prime}_{N}$.

######  Theorem 2.11 (Streaming lower bound for padded one-wise pairs,
[CGSV21, Theorem 2.11] (symmetric case)).

Let $(\mathcal{D}_{Y},\mathcal{D}_{N})$ be a padded one-wise pair. Then for
every $\epsilon>0$,
$(\beta_{S}(\mathcal{D}_{Y})+\epsilon,\gamma_{S}(\mathcal{D}_{N})-\epsilon)\textsf{-Max-
CSP}(f)$ requires $\Omega(\sqrt{n})$ space in the streaming setting.

We prove that Theorem 2.11 fails to rule out streaming
$(\frac{2}{9}+\epsilon)$-approximations to Max-$3$AND in the following sense:

######  Theorem 2.12.

There is no infinite sequence
$(\mathcal{D}_{Y}^{(1)},\mathcal{D}_{N}^{(1)}),(\mathcal{D}_{Y}^{(2)},\mathcal{D}_{N}^{(2)}),\ldots$
of padded one-wise pairs on $\Delta_{3}$ such that

$\lim_{t\to\infty}\frac{\beta_{\\{3\\}}(\mathcal{D}_{N}^{(t)})}{\gamma_{\\{3\\}}(\mathcal{D}_{Y}^{(t)})}=\frac{2}{9}.$

Theorem 2.12 is proven formally in Section 6; here is a proof outline:

###### Proof outline.

As discussed in Section 2.3, since $k=3$ is odd, to prove Theorem 1.2 we show,
using the max-min method, that $\mathcal{D}_{N}^{*}=(0,0,1,0)$ minimizes
$\frac{\beta_{\\{3\\}}(\cdot)}{\gamma_{\\{3\\},3}(\mu(\cdot))}$. We can show
that the corresponding $\gamma_{\\{3\\},3}$ value is achieved by
$\mathcal{D}_{Y}^{*}=(\frac{1}{3},0,0,\frac{2}{3})$. In particular,
$(\mathcal{D}_{N}^{*},\mathcal{D}_{Y}^{*})$ are not a padded one-wise pair.

We can show that the minimizer of $\gamma_{\\{3\\}}$ for a particular $\mu$ is
in general unique. Hence, it suffices to furthermore show that
$\mathcal{D}_{N}^{*}$ is the _unique_ minimizer of
$\frac{\beta_{\\{3\\}}(\cdot)}{\gamma_{\\{3\\},3}(\mu(\cdot))}$. For this
purpose, the max-min method is not sufficient because
$\frac{\lambda_{\\{3\\}}(\cdot,p^{*})}{\gamma_{\\{3\\},3}(\mu(\cdot))}$ is not
uniquely minimized at $\mathcal{D}_{N}^{*}$ (where we chose
$p^{*}=\frac{2}{3}$). Intuitively, this is because $p^{*}$ is not a good
enough estimate for the maximizer of
$\lambda_{\\{3\\}}(\mathcal{D}_{N},\cdot)$. To remedy this, we observe that
$\lambda_{\\{3\\}}((1,0,0,0),\cdot),\lambda_{\\{3\\}}((0,1,0,0),\cdot)$,
$\lambda_{\\{3\\}}((0,0,1,0),\cdot)$ and $\lambda_{\\{3\\}}((0,0,0,1),\cdot)$
are minimized at $0,\frac{1}{3},\frac{2}{3}$, and $1$, respectively. Hence, we
instead lower-bound $\lambda_{\\{3\\}}(\mathcal{D}_{N},\cdot)$ by evaluating
at $\frac{1}{3}\mathcal{D}_{N}\langle
1\rangle+\frac{2}{3}\mathcal{D}_{N}\langle 2\rangle+\mathcal{D}_{N}\langle
3\rangle$, which does suffice to prove the uniqueness of
$\mathcal{D}_{N}^{*}$. The theorem then follows from continuity arguments. ∎

Yet we still can achieve decent bounds using padded one-wise pairs:

######  Observation 2.13.

The padded one-wise pair
$\mathcal{D}_{N}=(0,0.45,0.45,0.1),\mathcal{D}_{Y}=(0.45,0,0,0.55)$
(discovered by numerical search) _does_ prove a streaming approximability
upper bound of $\approx.2362$ for $3$AND, which is still quite close to
$\alpha(\textsf{$3$AND})=\frac{2}{9}$.

##  3 Formulas for $\mu$, $\lambda_{S}$, and $\gamma_{S,k}$

In this section, we give explicit formulas for the quantities
$\mu(\mathcal{D})$, $\lambda_{S}(\mathcal{D},p)$, and $\gamma_{S,k}(\mu)$
(defined in Eqs. 2.2, 2.1 and 2.6, respectively) which will be used throughout
the rest of the paper. For $i\in[k]$, let
$\epsilon_{i,k}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}-1+\frac{2i}{k}$.

######  Lemma 3.1.

For any $\mathcal{D}\in\Delta_{k}$,

$\mu(\mathcal{D})=\sum_{i=0}^{k}\epsilon_{i,k}\,\mathcal{D}\langle i\rangle.$

###### Proof of Lemma 3.1.

By definition (Eq. 2.2),
$\mu(\mathcal{D})=\mathop{\mathbb{E}}_{\mathbf{b}\sim\mathcal{D}}[b_{1}]$. We
use linearity of expectation; the contribution of weight-$i$ vectors to
$\mu(\mathcal{D})$ is $\mathcal{D}\langle i\rangle\cdot\frac{1}{k}(i\cdot
1+(k-i)\cdot(-1))=\epsilon_{i,k}\,\mathcal{D}\langle i\rangle$. ∎

######  Lemma 3.2.

For any $\mathcal{D}\in\Delta_{k}$ and $p\in[0,1]$, we have

$\lambda_{S}(\mathcal{D},p)=\sum_{s\in
S}\sum_{i=0}^{k}\left(\sum_{j=\max\\{0,s-(k-i)\\}}^{\min\\{i,s\\}}{i\choose
j}{k-i\choose s-j}q^{s+i-2j}p^{k-s-i+2j}\right)\mathcal{D}\langle i\rangle$

where $q\stackrel{{\scriptstyle\mathrm{\small def}}}{{=}}1-p$.

###### Proof.

By linearity of expectation and symmetry, it suffices to fix $s$ and $i$ and
calculate, given a fixed string $\mathbf{a}=(a_{1},\ldots,a_{k})$ of Hamming
weight $i$ and a random string
$\mathbf{b}=(b_{1},\ldots,b_{k})\sim\mathsf{Bern}(p)^{k}$, the probability of
the event $\operatorname{wt}(\mathbf{a}\odot\mathbf{b})=s$.

Let $A=\textsf{supp}(\mathbf{a})=\\{t\in[k]:a_{t}=1\\}$ and similarly
$B=\textsf{supp}(\mathbf{b})$. We have $|A|=i$ and

$s=\operatorname{wt}(\mathbf{a}\odot\mathbf{b})=|A\cap B|+|([k]\setminus
A)\cap([k]\setminus B)|.$

Let $j=|A\cap B|$, and consider cases based on $j$.

Given fixed $j$, we must have $|A\cap B|=j$ and $|([k]\setminus
A)\cap([k]\setminus B)|=s-j$. Thus if $j$ satisfies $j\leq i,s-j\leq k-i,j\geq
0,j\leq s$, we have $\binom{i}{j}$ choices for $A\cap B$ and
$\binom{k-i}{s-j}$ choices for $([k]\setminus A)\cap([k]\setminus B)$;
together, these completely determine $B$. Moreover
$\operatorname{wt}(\mathbf{b})=|B|=|B\cap A|+|B\cap([k]\setminus
A)|=j+(k-i)-(s-j)=k-s-i+2j$, yielding the desired formula. ∎

######  Lemma 3.3.

Let $S\subseteq[k]$, and let $s$ be its smallest element and $t$ its largest
element (they need not be distinct). Then for $\mu\in[-1,1]$,

$\gamma_{S,k}(\mu)=\begin{cases}\frac{1+\mu}{1+\epsilon_{s,k}}&\mu\in[-1,\epsilon_{s,k})\\\
1&\mu\in[\epsilon_{s,k},\epsilon_{t,k}]\\\
\frac{1-\mu}{1-\epsilon_{t,k}}&\mu\in(\epsilon_{t,k},1]\end{cases}$

(which also equals
$\min\left\\{\frac{1+\mu}{1+\epsilon_{s,k}},1,\frac{1-\mu}{1-\epsilon_{t,k}}\right\\}$).

###### Proof.

For $\mu\in[-1,1]$, in (Eq. 2.6) we defined

$\gamma_{S,k}(\mu)=\sup_{\mathcal{D}_{Y}\in\Delta_{k}:\mu(\mathcal{D}_{Y})=\mu}\gamma_{S}(\mathcal{D}_{Y}),$

where by Eqs. 2.3 and 2.1), $\gamma_{S}(\mathcal{D}_{Y})=\sum_{i\in
S}\mathcal{D}_{Y}\langle i\rangle$. For $\mathcal{D}_{Y}\in\Delta_{k}$, let
$\textsf{supp}(\mathcal{D}_{Y})=\\{i\in[k]:\mathcal{D}_{Y}\langle
i\rangle>0\\}$. We handle cases based on $\mu$.

##### Case 1: $\mu\in[-1,\epsilon_{s,k}]$.

Our strategy is to reduce to the case
$\textsf{supp}(\mathcal{D}_{Y})\subseteq\\{0,s\\}$ while preserving the
marginal $\mu$ and (non-strictly) increasing the value of $\gamma_{S}$.

Consider the following operation on a distribution
$\mathcal{D}_{Y}\in\Delta_{k}$: For $u<v<w\in[k]$, increase
$\mathcal{D}_{Y}\langle u\rangle$ by $\mathcal{D}_{Y}\langle
v\rangle\,\frac{w-v}{w-u}$, increase $\mathcal{D}_{Y}\langle w\rangle$ by
$\mathcal{D}_{Y}\langle v\rangle\,\frac{v-u}{w-u}$, and set
$\mathcal{D}_{Y}\langle v\rangle$ to zero. Note that this results in a new
distribution with the same marginal, since

$\mathcal{D}_{Y}\langle
v\rangle\frac{w-v}{w-u}\epsilon_{u,k}+\mathcal{D}_{Y}\langle
v\rangle\frac{v-u}{w-u}\epsilon_{w,k}=\mathcal{D}_{Y}\langle
v\rangle\,\epsilon_{v,k}.$

Given an initial distribution $\mathcal{D}_{Y}$, we can apply this operation
to zero out $\mathcal{D}_{Y}\langle v\rangle$ for $v\in\\{1,\ldots,s-1\\}$ by
redistributing to $\mathcal{D}_{Y}\langle 0\rangle$ and
$\mathcal{D}_{Y}\langle s\rangle$, preserving the marginal and only increasing
the value of $\gamma_{S}$ (since $v\not\in S$ while $s\in S$). Similarly, we
can redistribute $\mathcal{D}_{Y}\langle v\rangle$ to $\mathcal{D}_{Y}\langle
t\rangle$ and $\mathcal{D}_{Y}\langle k\rangle$ when
$v\in\\{t+1,\ldots,k-1\\}$, and to $\mathcal{D}_{Y}\langle s\rangle$ and
$\mathcal{D}_{Y}\langle t\rangle$ when $v\in\\{s+1,\ldots,t-1\\}$. Thus, we
need only consider the case
$\textsf{supp}(\mathcal{D})\subseteq\\{0,s,t,k\\}$. We assume for simplicity
that $0,s,t,k$ are distinct.

By definition of $\epsilon_{i,k}$ we have

$\mu(\mathcal{D})=-\mathcal{D}_{Y}\langle 0\rangle+\mathcal{D}_{Y}\langle
s\rangle\left(-1+\frac{2s}{k}\right)+\mathcal{D}_{Y}\langle
t\rangle\left(-1+\frac{2t}{k}\right)+\mathcal{D}_{Y}\langle
k\rangle\leq-1+\frac{2s}{k}$

(by assumption for this case). Substituting $\mathcal{D}_{Y}\langle
s\rangle=1-\mathcal{D}_{Y}\langle 0\rangle-\mathcal{D}_{Y}\langle
t\rangle-\mathcal{D}_{Y}\langle k\rangle$ and multiplying through by
$\frac{k}{2}$, we have

$k\mathcal{D}_{Y}\langle k\rangle-s\mathcal{D}_{Y}\langle
0\rangle-s\mathcal{D}_{Y}\langle t\rangle-s\mathcal{D}_{Y}\langle
k\rangle+t\mathcal{D}_{Y}\langle t\rangle\leq 0;$

defining $\delta=\mathcal{D}_{Y}\langle
t\rangle(\frac{t}{s}-1)+\mathcal{D}_{Y}\langle k\rangle(\frac{k}{s}-1)$, we
can rearrange to get $\mathcal{D}_{Y}\langle 0\rangle\geq\delta$. Then given
$\mathcal{D}_{Y}$, we can zero out $\mathcal{D}_{Y}\langle t\rangle$ and
$\mathcal{D}_{Y}\langle k\rangle$, decrease $\mathcal{D}_{Y}\langle 0\rangle$
by $\delta$, and correspondingly increase $\mathcal{D}_{Y}\langle s\rangle$ by
$\mathcal{D}_{Y}\langle t\rangle+\mathcal{D}_{Y}\langle k\rangle+\delta$. This
preserves the marginal since

$(\delta+\mathcal{D}_{Y}\langle t\rangle+\mathcal{D}_{Y}\langle
k\rangle)\,\epsilon_{s,k}=-\delta+\mathcal{D}_{Y}\langle
t\rangle\,\epsilon_{t,k}+\mathcal{D}_{Y}\langle k\rangle$

and can only increase $\gamma_{S}$.

Thus, it suffices to only consider the case
$\textsf{supp}(\mathcal{D}_{Y})\subseteq\\{0,s\\}$. This uniquely determines
$\mathcal{D}_{Y}$ (because $\mu$ is fixed); we have $\mathcal{D}_{Y}\langle
0\rangle=\frac{\epsilon_{s,k}-\mu}{\epsilon_{s,k}+1}$ and
$\mathcal{D}_{Y}\langle s\rangle=\frac{1+\mu}{\epsilon_{s,k}+1}$, yielding the
desired value of $\gamma_{S}$.

##### Case 2: $\mu\in[\epsilon_{s,k},\epsilon_{t,k}]$.

We simply construct $\mathcal{D}_{Y}$ with $\mathcal{D}_{Y}\langle
s\rangle=\frac{\epsilon_{t,k}-\mu}{\epsilon_{s,k}-\epsilon_{t,k}}$ and
$\mathcal{D}_{Y}\langle
t\rangle=\frac{\mu-\epsilon_{s,k}}{\epsilon_{s,k}-\epsilon_{t,k}}$; we have
$\mu(\mathcal{D}_{Y})=\mu$ and $\gamma_{S}(\mathcal{D}_{Y})=1$.

##### Case 3: $\mu\in[\epsilon_{t,k},1]$.

Following the symmetric logic to Case 1, we consider $\mathcal{D}_{Y}$
supported on $\\{t,k\\}$ and set $\mathcal{D}_{Y}\langle
t\rangle=\frac{1-\mu}{1-\epsilon_{t,k}}$ and $\mathcal{D}_{Y}\langle
k\rangle=\frac{\mu-\epsilon_{t,k}}{1-\epsilon_{t,k}}$, yielding
$\mu(\mathcal{D}_{Y})=\mu$ and
$\gamma_{S}(\mathcal{D}_{Y})=\mathcal{D}_{Y}\langle t\rangle$. ∎

##  4 Analysis of $\alpha(k\textsf{AND})$

In this section, we prove Theorem 1.2 (on the sketching approximability of
$\textsf{Max-}k\textsf{AND}$). Recall that in Eq. 1.1, we defined

$\alpha^{\prime}_{k}=\left(\frac{(k-1)(k+1)}{4k^{2}}\right)^{(k-1)/2}.$

Theorem 1.2 follows immediately from the following two lemmas:

######  Lemma 4.1.

For all odd $k\geq 3$, $\alpha(k\textsf{AND})\leq\alpha^{\prime}_{k}$. For all
even $k\geq 2$, $\alpha(k\textsf{AND})\leq 2\alpha^{\prime}_{k+1}$.

######  Lemma 4.2.

For all odd $k\geq 3$, $\alpha(k\textsf{AND})\geq\alpha^{\prime}_{k}$. For all
even $k\geq 2$, $\alpha(k\textsf{AND})\geq 2\alpha^{\prime}_{k+1}$.

To begin, we give explicit formulas for $\gamma_{\\{k\\},k}(\mu(\mathcal{D}))$
and $\lambda_{\\{k\\}}(\mathcal{D},p)$. Note that the smallest element of
$\\{k\\}$ is $k$, and $\epsilon_{k,k}=1$. Thus, for
$\mathcal{D}\in\Delta_{k}$, we have by Lemmas 3.3 and 3.1 that

$\gamma_{\\{k\\},k}(\mu(\mathcal{D}))=\frac{1+\sum_{i=0}^{k}(-1+\frac{2i}{k})\,\mathcal{D}\langle
i\rangle}{2}=\sum_{i=0}^{k}\frac{i}{k}\,\mathcal{D}\langle i\rangle.$ (4.3)

Similarly, we can apply Lemma 3.2 with $s=k$; for each $i\in\\{0\\}\cup[k]$,
$\max\\{0,s-(k-i)\\}=\min\\{i,k\\}=i$, so we need only consider $j=i$, and
then $\binom{i}{j}=\binom{k-i}{s-j}=1$. Thus, for $q=1-p$, we have

$\lambda_{\\{k\\}}(\mathcal{D},p)=\sum_{i=0}^{k}q^{k-i}p^{i}\,\mathcal{D}\langle
i\rangle$ (4.4)

Now, we prove Lemma 4.1 directly:

###### Proof of Lemma 4.1.

Consider the case where $k$ is odd. Define $\mathcal{D}_{N}^{*}$ by
$\mathcal{D}_{N}^{*}\langle\frac{k+1}{2}\rangle=1$ and let
$p^{*}=\frac{1}{2}+\frac{1}{2k}$. Since

$\alpha(k\textsf{AND})\leq\frac{\beta_{\\{k\\}}(\mathcal{D}_{N}^{*})}{\gamma_{\\{k\\},k}(\mu(\mathcal{D}_{N}^{*}))}\text{
and
}\beta_{\\{k\\}}(\mathcal{D}_{N})=\sup_{p\in[0,1]}\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},p),$

by Eqs. 2.8 and 2.3, respectively, it suffices to check that $p^{*}$ maximizes
$\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},\cdot)$ and

$\frac{\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},p^{*})}{\gamma_{\\{k\\},k}(\mu(\mathcal{D}_{N}^{*}))}=\alpha^{\prime}_{k}.$

Indeed, by Eq. 4.4,

$\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},p)=(1-p)^{(k-1)/2}p^{(k+1)/2}.$

To show $p^{*}$ maximizes $\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},\cdot)$, we
calculate its derivative:

$\frac{d}{dp}\left[(1-p)^{(k-1)/2}p^{(k+1)/2}\right]=-(1-p)^{(k-3)/2}p^{(k-1)/2}\left(kp-\frac{k+1}{2}\right),$

which has zeros only at $0,1,$ and $p^{*}$. Thus,
$\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},\cdot)$ has critical points only at
$0,1,$ and $p^{*}$, and it is maximized at $p^{*}$ since it vanishes at $0$
and $1$. Finally, by Eqs. 4.3 and 4.4 and the definition of
$\alpha^{\prime}_{k}$,

$\frac{\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},p^{*})}{\gamma_{\\{k\\},k}(\mu(\mathcal{D}_{N}^{*}))}=\frac{\left(\frac{1}{2}-\frac{1}{2k}\right)^{(k-1)/2}\left(\frac{1}{2}+\frac{1}{2k}\right)^{(k+1)/2}}{\frac{1}{2}\left(1+\frac{1}{k}\right)}=\alpha^{\prime}_{k},$

as desired.

Similarly, consider the case where $k$ is even; here, we define
$\mathcal{D}_{N}^{*}$ by
$\mathcal{D}_{N}^{*}\langle\frac{k}{2}\rangle=\frac{\left(\frac{k}{2}+1\right)^{2}}{\left(\frac{k}{2}\right)^{2}+\left(\frac{k}{2}+1\right)^{2}}$
and
$\mathcal{D}_{N}^{*}\langle\frac{k}{2}+1\rangle=\frac{\left(\frac{k}{2}\right)^{2}}{\left(\frac{k}{2}\right)^{2}+\left(\frac{k}{2}+1\right)^{2}}$,
and set $p^{*}=\frac{1}{2}+\frac{1}{2(k+1)}$. Using Eq. 4.4 to calculate the
derivative of $\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},\cdot)$ yields

$\frac{d}{dp}\left[\frac{\left(\frac{k}{2}+1\right)^{2}}{\left(\frac{k}{2}\right)^{2}+\left(\frac{k}{2}+1\right)^{2}}(1-p)^{k/2}p^{k/2}+\frac{\left(\frac{k}{2}\right)^{2}}{\left(\frac{k}{2}\right)^{2}+\left(\frac{k}{2}+1\right)^{2}}(1-p)^{k/2-1}p^{k/2+1}\right]\\\
=-\frac{k}{2+2k+2k^{2}}(1-p)^{k/2-2}p^{k/2-1}\left(\frac{k}{2}+1-2p\right)\left((k+1)p-\left(\frac{k}{2}+1\right)\right),$

so $\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},\cdot)$ has critical points at
$0,1,\frac{1}{2}+\frac{k}{4}$. and $p^{*}$; $p^{*}$ is the only critical point
in the interval $[0,1]$ for which
$\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},\cdot)$ is positive, and hence is its
maximum. Finally, it can be verified algebraically using Eqs. 4.3 and 4.4 that
$\frac{\lambda_{\\{k\\}}(\mathcal{D}_{N}^{*},p^{*})}{\gamma_{\\{k\\},k}(\mu(\mathcal{D}_{N}^{*}))}=2\alpha^{\prime}_{k+1}$,
as desired. ∎

We prove Lemma 4.2 using the max-min method. We rely on the following
proposition which is a simple inequality for optimizing ratios of linear
functions, which we prove in Appendix A:

######  Proposition 4.5.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be defined by the equation
$f(\mathbf{x})=\frac{\mathbf{a}\cdot\mathbf{x}}{\mathbf{b}\cdot\mathbf{x}}$
for some $\mathbf{a},\mathbf{b}\in\mathbb{R}_{\geq 0}^{n}$. For every
$\mathbf{y}(1),\ldots,\mathbf{y}(r)\in\mathbb{R}_{\geq 0}^{n}$, and every
$\mathbf{x}=\sum_{i=1}^{r}\alpha_{i}\mathbf{y}(i)$ with each $x_{i}\geq 0$, we
have $f(\mathbf{x})\geq\min_{i}f(\mathbf{y}(i))$. In particular, taking $r=n$
and $\mathbf{y}(1),\ldots,\mathbf{y}(n)$ as the standard basis for
$\mathbb{R}^{n}$, for every $\mathbf{x}\in\mathbb{R}_{\geq 0}^{n}$, we have
$f(\mathbf{x})\geq\min_{i}\frac{a_{i}}{b_{i}}$.

###### Proof of Lemma 4.2.

First, suppose $k\geq 3$ is odd. Set
$p^{*}=\frac{1}{2}+\frac{1}{2k}=\frac{k+1}{2k}$. We want to show that

$\displaystyle\alpha^{\prime}_{k}$
$\displaystyle\leq\inf_{\mathcal{D}_{N}\in\Delta_{k}}\frac{\lambda_{\\{k\\}}(\mathcal{D}_{N},p^{*})}{\gamma_{\\{k\\},k}(\mu(\mathcal{D}_{N}))}$
(max-min inequality, i.e., Eq. 2.9)
$\displaystyle=\inf_{\mathcal{D}_{N}\in\Delta_{k}}\frac{\sum_{i=0}^{k}(1-p^{*})^{k-i}(p^{*})^{i}\,\mathcal{D}_{N}\langle
i\rangle}{\sum_{i=0}^{k}\frac{i}{k}\,\mathcal{D}_{N}\langle i\rangle}.$ (Eqs.
4.3 and 4.4)

By Proposition 4.5, it suffices to check that

$\forall
i\in\\{0\\}\cup[k],\quad(1-p^{*})^{k-i}(p^{*})^{i}\geq\alpha^{\prime}_{k}\cdot\frac{i}{k}.$

By definition of $\alpha^{\prime}_{k}$, we have that
$\alpha^{\prime}_{k}=(1-p^{*})^{(k-1)/2}(p^{*})^{(k-1)/2}$. Defining
$r=\frac{p^{*}}{1-p^{*}}=\frac{k+1}{k-1}$ (so that $p^{*}=r(1-p^{*})$),
factoring out $(1-p^{*})^{k}$, and simplifying, we can rewrite our desired
inequality as

$\forall i\in\\{0\\}\cup[k],\quad\frac{1}{2}(k-1)r^{i-\frac{k-1}{2}}\geq i.$
(4.6)

When $i=\frac{k+1}{2}$ or $\frac{k-1}{2}$, we have equality in Eq. 4.6. We
extend to the other values of $i$ by induction. Indeed, when
$i\geq\frac{k+1}{2}$, then “$i$ satisfies Eq. 4.6” implies “$i+1$ satisfies
Eq. 4.6” because $ri\geq i+1$, and when $i\leq\frac{k-1}{2}$, then “$i$
satisfies Eq. 4.6” implies “$i-1$ satisfies Eq. 4.6” because $\frac{1}{r}i\geq
i-1$.

Similarly, in the case where $k\geq 2$ is even, we set
$p^{*}=\frac{1}{2}+\frac{1}{2(k+1)}$ and
$r=\frac{p^{*}}{1-p^{*}}=\frac{k+2}{k}$. In this case, for
$i\in\\{0\\}\cup[k]$ the following analogue of Eq. 4.6 can be derived:

$\forall i\in\\{0\\}\cup[k],\quad\frac{1}{2}kr^{i-\frac{k}{2}}\geq i,$

and these inequalities follow from the same inductive argument. ∎

##  5 Further analyses of $\alpha(f)$ for symmetric Boolean functions $f$

###  5.1 $\mathsf{Th}^{k-1}_{k}$ for even $k$

In this subsection, we prove Theorem 1.4 (on the sketching approximability of
$\mathsf{Th}^{k-1}_{k}$ for even $k\geq 2$). It is necessary and sufficient to
prove the following two lemmas:

######  Lemma 5.1.

For all even $k\geq 2$,
$\alpha(\mathsf{Th}^{k-1}_{k})\leq\frac{k}{2}\alpha_{k-1}^{\prime}$.

######  Lemma 5.2.

For all even $k\geq 2$,
$\alpha(\mathsf{Th}^{k-1}_{k})\geq\frac{k}{2}\alpha_{k-1}^{\prime}$.

Firstly, we give explicit formulas for $\gamma_{\\{k-1,k\\},k}$ and
$\lambda_{\\{k-1,k\\}}$. We have $\mathsf{Th}_{k}^{k-1}=f_{\\{k-1,k\\},k}$,
and $\epsilon_{k-1,k}=-1+\frac{2(k-1)}{k}=1-\frac{2}{k}$. Thus, Lemmas 3.3 and
3.1 give

$\gamma_{\\{k-1,k\\},k}(\mu(\mathcal{D}))=\min\left\\{\frac{1+\sum_{i=0}^{k}(-1+\frac{2i}{k})\,\mathcal{D}\langle
i\rangle}{2-\frac{2}{k}},1\right\\}=\min\left\\{\sum_{i=0}^{k}\frac{i}{k-1}\,\mathcal{D}\langle
i\rangle,1\right\\}.$ (5.3)

Next, we calculate $\lambda_{\\{k-1,k\\}}(\mathcal{D},p)$ with Lemma 3.2. Let
$q=1-p$, and let us examine the coefficient on $\mathcal{D}\langle i\rangle$.
$s=k$ contributes $q^{k-i}p^{k}$. In the case $i\leq k-1$, $s=k-1$ contributes
$(k-i)q^{k-i-1}p^{i+1}$ for $j=i$, and in the case $i\geq 1$, $s=k-1$
contributes $iq^{k-i+1}p^{i-1}$ for $j=i-1$. Thus, altogether we can write

$\lambda_{\\{k-1,k\\}}(\mathcal{D},p)=\sum_{i=0}^{k}q^{k-i-1}p^{i-1}\left((k-i)p^{2}+pq+iq^{2}\right)\,\mathcal{D}\langle
i\rangle.$ (5.4)

Now, we prove Lemmas 5.1 and 5.2.

###### Proof of Lemma 5.1.

As in the proof of Lemma 4.1, it suffices to construct $\mathcal{D}_{N}^{*}$
and $p^{*}$ such that $p^{*}$ maximizes
$\lambda_{\\{k-1,k\\}}(\mathcal{D}_{N}^{*},\cdot)$ and
$\frac{\lambda_{\\{k-1,k\\}}(\mathcal{D}_{N}^{*},p^{*})}{\gamma_{\\{k-1,k\\},k}(\mu(\mathcal{D}_{N}^{*}))}=\frac{k}{2}\alpha^{\prime}_{k-1}$.

We again let $p^{*}=\frac{1}{2}+\frac{1}{2(k-1)}$, but define
$\mathcal{D}_{N}^{*}$ by
$\mathcal{D}_{N}^{*}\langle\frac{k}{2}\rangle=\frac{\left(\frac{k}{2}\right)^{2}}{\left(\frac{k}{2}\right)^{2}+\left(\frac{k}{2}-1\right)^{2}}$
and
$\mathcal{D}_{N}^{*}\langle\frac{k}{2}+1\rangle=\frac{\left(\frac{k}{2}-1\right)^{2}}{\left(\frac{k}{2}\right)^{2}+\left(\frac{k}{2}-1\right)^{2}}$.
By Eq. 5.4, the derivative of
$\lambda_{\\{k-1,k\\}}(\mathcal{D}_{N}^{*},\cdot)$ is now

$\frac{d}{dp}\Bigg{[}\frac{\left(\frac{k}{2}\right)^{2}}{\left(\frac{k}{2}\right)^{2}+\left(\frac{k}{2}-1\right)^{2}}(1-p)^{k/2-1}p^{k/2-1}\left(\frac{k}{2}p^{2}+pq+\frac{k}{2}q^{2}\right)+\\\
\frac{\left(\frac{k}{2}-1\right)^{2}}{\left(\frac{k}{2}\right)^{2}+\left(\frac{k}{2}-1\right)^{2}}(1-p)^{k/2-2}p^{k/2}\left(\left(\frac{k}{2}-1\right)p^{2}+pq+\left(\frac{k}{2}+1\right)q^{2}\right)\Bigg{]}\\\
=-\frac{1}{8(k^{2}-2k+2)}(1-p)^{k/2-3}p^{k/2-2}(-k+(2(k-1)p)\xi(p),$

where $\xi(p)$ is the cubic

$\xi(p)=-8k(k-1)p^{3}+2(k^{3}+k^{2}+6k-12)p^{2}-2(k^{3}-4)p+k^{2}(k-2).$

Thus, $\lambda_{\\{k-1,k\\}}$’s critical points on the interval $[0,1]$ are
$0,1,p^{*}$ and any roots of $\xi$ in this interval. We claim that $\xi$ has
no additional roots in the interval $(0,1)$. This can be verified directly by
calculating roots for $k=2,4$, so assume WLOG $k\geq 6$.

Suppose $\xi(p)=0$ for some $p\in(0,1)$, and let
$x=\frac{1}{p}-1\in(0,\infty)$. Then $p=\frac{1}{1+x}$; plugging this in for
$p$ and multiplying through by $(x+1)^{3}$ gives the new cubic

$(k^{3}-2k^{2})x^{3}+(k^{3}-6k^{2}+8)x^{2}+(k^{3}-4k^{2}+12k-8)x+(k^{3}-8k^{2}+20k-16)=0$
(5.5)

whose coefficients are cubic in $k$. It can be verified by calculating the
roots of each coefficient of $x$ in Eq. 5.5 that all coefficients are positive
for $k\geq 6$. Thus, Eq. 5.5 cannot have roots for positive $x$, a
contradiction. Hence $\lambda_{\\{k-1,k\\}}(\mathcal{D}_{N}^{*},\cdot)$ is
maximized at $p^{*}$. Finally, it can be verified that
$\frac{\lambda_{\\{k-1,k\\}}(\mathcal{D}_{N}^{*},p^{*})}{\gamma_{\\{k-1,k\\},k}(\mu(\mathcal{D}_{N}^{*}))}=\frac{k}{2}\alpha^{\prime}_{k-1}$,
as desired. ∎

###### Proof of Lemma 5.2.

Define $p^{*}=\frac{1}{2}+\frac{1}{2(k-1)}$. Following the proof of Lemma 4.2
and using the lower bound
$\gamma_{\\{k-1,k\\},k}(\mu(\mathcal{D}_{N}))\leq\sum_{i=0}^{k}\frac{i}{k-1}\,\mathcal{D}_{N}\langle
i\rangle$, it suffices to show that

$\frac{k}{2}\alpha^{\prime}_{k-1}\leq\inf_{\mathcal{D}_{N}\in\Delta_{k}}\frac{\sum_{i=0}^{k}(1-p^{*})^{k-i-1}(p^{*})^{i-1}((k-i)(p^{*})^{2}+p^{*}(1-p^{*})+i(1-p^{*})^{2})\,\mathcal{D}_{N}\langle
i\rangle}{\sum_{i=0}^{k}\frac{i}{k-1}\,\mathcal{D}_{N}\langle i\rangle}$

for which by Proposition 4.5, it in turn suffices to prove that for each
$i\in\\{0\\}\cup[k]$,

$\frac{k}{2}\alpha^{\prime}_{k-1}\frac{i}{k-1}\leq(1-p^{*})^{k-i-1}(p^{*})^{i-1}((k-i)(p^{*})^{2}+p^{*}(1-p^{*})+i(1-p^{*})^{2}).$

We again observe that
$\alpha^{\prime}_{k-1}=(1-p^{*})^{k/2-1}(p^{*})^{k/2-1}$, define
$r=\frac{p^{*}}{1-p^{*}}=\frac{k}{k-2}$, and factor out $(1-p^{*})^{k-1}$,
which simplifies our desired inequality to

$\frac{1}{2}r^{i-\frac{k}{2}-1}\cdot\frac{k-2}{k-1}\left(i+r+(k-i)r^{2}\right)\geq
i.$ (5.6)

for each $i\in\\{0\\}\cup[k]$. Again, we assume $k\geq 6$ WLOG; the bases
cases $i=\frac{k}{2}-1,\frac{k}{2}$ can be verified directly, and we proceed
by induction. If Eq. 5.6 holds for $i$, and we seek to prove it for $i+1$, it
suffices to cross-multiply and instead prove the inequality

$r(i+1+r+(k-(i+1))r^{2})i\geq(i+1)(i+r+(k-i)r^{2}),$

which simplifies to

$(k-2i)(k-1)(k^{2}-4i-4)\leq 0,$

which holds whenever $\frac{k}{2}\leq i\leq\frac{k^{2}-4}{4}$ (and
$\frac{k^{2}-4}{4}\geq k$ for all $k\geq 6$). The other direction (where
$i\leq\frac{k}{2}-1$ and we induct downwards) is similar. ∎

######  Observation 5.7.

For $\mathsf{Th}^{3}_{4}$ the optimal
$\mathcal{D}_{N}^{*}=(0,0,\frac{4}{5},\frac{1}{5},0)$ does participate in a
padded one-wise pair with
$\mathcal{D}_{Y}^{*}=(\frac{4}{15},0,0,\frac{11}{15},0)$ (given by
$\mathcal{D}_{0}=(0,0,0,1,0)$, $\tau=\frac{1}{5}$,
$\mathcal{D}^{\prime}_{N}=(0,0,1,0,0)$, and
$\mathcal{D}^{\prime}_{Y}=(\frac{4}{15},0,0,\frac{8}{15},0)$) so we can rule
out _streaming_ $(\frac{4}{9}+\epsilon)$-approximations to $\textsf{Max-
CSP}(\mathsf{Th}^{3}_{4})$ in $o(\sqrt{n})$ space.

###  5.2 $\mathsf{Ex}^{(k+1)/2}_{k}$ for (small) odd $k$

In this section, we prove bounds on the sketching approximability of
$\mathsf{Ex}^{(k+1)/2}_{k}$ for odd $k\in\\{3,\dots,51\\}$. Define
$\mathcal{D}_{0,k}\in\Delta_{k}$ by $\mathcal{D}_{0,k}\langle
0\rangle=\frac{k-1}{2k}$ and $\mathcal{D}_{0,k}\langle
k\rangle=\frac{k+1}{2k}$. We prove the following two lemmas:

######  Lemma 5.8.

For all odd $k\geq 3$,
$\alpha(\mathsf{Ex}^{(k+1)/2}_{k})\leq\lambda_{\\{\frac{k+1}{2}\\}}(\mathcal{D}_{0,k},p^{\prime}_{k})$,
where $p^{\prime}_{k}\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\frac{3k-k^{2}+\sqrt{4k+k^{2}-2k^{3}+k^{4}}}{4k}$.

######  Lemma 5.9.

The following holds for all odd $k\in\\{3,\ldots,51\\}$. For all $p\in[0,1]$,
the expression
$\frac{\lambda_{\\{\frac{k+1}{2}\\}}(\cdot,p)}{\gamma_{\\{\frac{k+1}{2}\\},k}(\mu(\cdot))}$
is minimized at $\mathcal{D}_{0,k}$.

We begin by writing an explicit formula for $\lambda_{\\{\frac{k+1}{2}\\}}$.
Lemma 3.2 gives

$\lambda_{\\{\frac{k+1}{2}\\}}(\mathcal{D},p)=\sum_{i=0}^{k}\left(\sum_{j=\max\\{0,i-\frac{k-1}{2}\\}}^{\min\\{i,\frac{k+1}{2}\\}}\binom{i}{j}\binom{k}{\frac{k+1}{2}-j}(1-p)^{(k+1)/2+i-2j}p^{(k-1)/2-i+2j}\right)\,\mathcal{D}\langle
i\rangle.$

For $i\leq\frac{k-1}{2}$, the sum over $j$ goes from $0$ to $i$, and for
$i\geq\frac{k+1}{2}$, it goes from $i-\frac{k-1}{2}$ to $\frac{k+1}{2}$. Thus,
plugging in $\mathcal{D}_{0,k}$, we get:

$\lambda_{\\{\frac{k+1}{2}\\}}(\mathcal{D}_{0,k},p)=\binom{k}{\frac{k+1}{2}}\left(\frac{k-1}{2k}(1-p)^{(k+1)/2}p^{(k-1)/2}+\frac{k+1}{2k}(1-p)^{(k-1)/2}p^{(k+1)/2}\right).$
(5.10)

By Lemmas 3.3 and 3.1,
$\gamma_{\\{\frac{k+1}{2}\\},k}(\mu(\mathcal{D}_{0,k}))=\gamma_{\\{\frac{k+1}{2}\\},k}(\frac{1}{k})=1$.
Thus, Lemmas 5.8 and 5.9 together imply the following theorem:

######  Theorem 5.11.

For odd $k\in\\{3,\ldots,51\\}$,

$\alpha(\mathsf{Ex}^{(k+1)/2}_{k})=\binom{k}{\frac{k+1}{2}}\left(\frac{k-1}{2k}(1-p^{\prime}_{k})^{(k+1)/2}(p^{\prime}_{k})^{(k-1)/2}+\frac{k+1}{2k}(1-p^{\prime}_{k})^{(k-1)/2}(p^{\prime}_{k})^{(k+1)/2}\right),$

where $p^{\prime}_{k}=\frac{3k-k^{2}+\sqrt{4k+k^{2}-2k^{3}+k^{4}}}{4k}$ as in
Lemma 5.8.

Recall that $\rho(f_{(k+1)/2,k})=\binom{k}{\frac{k+1}{2}}2^{-k}$. Although we
currently lack a lower bound on $\alpha(\mathsf{Ex}^{(k+1)/2}_{k})$ for large
odd $k$, the upper bound from Lemma 5.8 suffices to prove Theorem 1.6, i.e.,
it can be verified that

$\lim_{k\text{
odd}\to\infty}\frac{\binom{k}{\frac{k+1}{2}}\left(\frac{k-1}{2k}(1-p^{\prime}_{k})^{(k+1)/2}(p^{\prime}_{k})^{(k-1)/2}+\frac{k+1}{2k}(1-p^{\prime}_{k})^{(k-1)/2}(p^{\prime}_{k})^{(k+1)/2}\right)}{\rho(\mathsf{Ex}^{(k+1)/2}_{k})}=1.$

We remark that for $\mathsf{Ex}^{(k+1)/2}_{k}$, our lower bound (Lemma 5.9) is
_stronger_ than what we were able to prove for $k\textsf{AND}$ (Lemma 4.2) and
$\mathsf{Th}^{k-1}_{k}$ (Lemma 5.2) because the inequality holds regardless of
$p$. This is fortunate for us, as the optimal $p^{*}$ from Lemma 5.8 is rather
messy.666The analogous statement is false for e.g. $3$AND, where we had
$\mathcal{D}_{N}^{*}=(0,0,1,0)$, but at $p=\frac{3}{4}$,
$\frac{\lambda_{\\{3\\}}((0,\frac{1}{2},\frac{1}{2},0),\frac{3}{4})}{\gamma_{\\{3\\},3}(\mu(0,\frac{1}{2},\frac{1}{2},0))}=\frac{3}{16}\leq\frac{27}{128}=\frac{\lambda_{\\{3\\}}((0,0,1,0),\frac{3}{4})}{\gamma_{\\{3\\},3}(\mu(0,0,1,0))}.$
It remains to prove Lemmas 5.8 and 5.9.

###### Proof of Lemma 5.8.

Taking the derivative with respect to $p$ of Eq. 5.10 yields

$\frac{d}{dp}\left[\lambda_{\\{\frac{k+1}{2}\\}}(\mathcal{D}_{0,k},p)\right]=-\frac{1}{4k}\binom{k}{\frac{k+1}{2}}(pq)^{(k-3)/2}(4kp^{2}+(2k^{2}-6k)p+(-k^{2}+2k-1)),$

where $q=1-p$. Thus, $\lambda_{\\{\frac{k+1}{2}\\}}(\mathcal{D}_{0,k},\cdot)$
has critical points at $p=0,1,p^{\prime}_{k},$ and
$\frac{3k-k^{2}-\sqrt{4k+k^{2}-2k^{3}+k^{4}}}{4k}$. This last value is
nonpositive for all $k\geq 0$ (since
$(3k-k^{2})^{2}-(4k+k^{2}-2k^{3}+k^{4})=-4k(k-1)^{2}$). ∎

The proof of our lower bound (Lemma 5.9) is slightly different than those of
our earlier lower bounds (i.e., Lemmas 4.2 and 5.2) in the following sense.
For $i\in\\{0\\}\cup[k]$, let $\mathcal{D}_{i}\in\Delta_{k}$ be defined by
$\mathcal{D}_{i}\langle i\rangle=1$. For $k\textsf{AND}$ (Lemma 4.2), we used
the fact that
$\frac{\lambda_{\\{k\\}}(\cdot,p^{*})}{\gamma_{\\{k\\},k}(\mu(\cdot))}$ is a
ratio of linear functions, and thus using Proposition 4.5, it is sufficient to
verify the lower bound at $\mathcal{D}_{0},\ldots,\mathcal{D}_{k}$. For
$\mathsf{Th}_{k}^{k-1}$ (Lemma 5.2),
$\frac{\lambda_{\\{k-1,k\\}}(\cdot,p^{*})}{\gamma_{\\{k-1,k\\},k}(\mu(\cdot))}$
is _not_ a ratio of linear functions, because the denominator
$\gamma_{\\{k-1,k\\},k}(\mu(\mathcal{D}))=\min\\{\sum_{i=0}^{k}\frac{i}{k-1}\,\mathcal{D}\langle
i\rangle,1\\}$ is not linear over $\Delta_{k}$. However, we managed to carry
out the proof by upper-bounding the denominator with the linear function
$\gamma^{\prime}(\mathcal{D})=\sum_{i=0}^{k}\frac{i}{k-1}\mathcal{D}\langle
i\rangle$, and then invoking Proposition 4.5 (again, to show that it suffices
to verify the lower bound at $\mathcal{D}_{0},\ldots,\mathcal{D}_{k}$).

For $\mathsf{Ex}^{(k+1)/2}_{k}$, we show that it suffices to verify the lower
bound on a larger (but still finite) set of distributions.

###### Proof of Lemma 5.9.

Recalling that $\epsilon_{(k+1)/2,k}=\frac{1}{k}$, let
$\Delta^{+}_{k}=\\{\mathcal{D}\in\Delta_{k}:\mu(\mathcal{D})\leq\frac{1}{k}\\}$
and
$\Delta^{-}_{k}=\\{\mathcal{D}\in\Delta_{k}:\mu(\mathcal{D})\geq\frac{1}{k}\\}$.
Note that $\Delta_{k}^{+}\cup\Delta_{k}^{-}=\Delta_{k}$, and restricted to
either $\Delta_{k}^{+}$ or $\Delta_{k}^{-}$,
$\gamma_{\\{\frac{k+1}{2}\\},k}(\mu(\cdot))$ is linear and thus we can apply
Proposition 4.5 to
$\frac{\lambda_{\\{k-1,k\\}}(\cdot,p^{*})}{\gamma_{\\{k-1,k\\},k}(\mu(\cdot))}$.

Let $\mathcal{D}_{i,j}\in\Delta_{k}$, for $i<\frac{k+1}{2},j>\frac{k+1}{2}$,
be defined by $\mathcal{D}_{i,j}\langle i\rangle=\frac{2j-(k+1)}{2(j-i)}$ and
$\mathcal{D}_{i,j}\langle j\rangle=\frac{(k+1)-2i}{2(j-i)}$. Note that
$\mu(\mathcal{D}_{i,j})=\frac{1}{k}$ for each $i,j$. We claim that
$\\{\mathcal{D}_{i}\\}_{i\leq\frac{k+1}{2}}\cup\\{\mathcal{D}_{i,j}\\}$ are
the extreme points of $\Delta_{k}^{+}$, or more precisely, that every
distribution $\mathcal{D}\in\Delta_{k}^{+}$ can be represented as a convex
combination of these distributions. Indeed, this follows constructively from
the procedure which, given a distribution $\mathcal{D}$, subtracts from each
$\mathcal{D}\langle i\rangle$ for $i<\frac{k+1}{2}$ (adding to the coefficient
of the corresponding $\mathcal{D}_{i}$) until the marginal of the
(renormalized) distribution is $\frac{1}{k}$, and then subtracts from pairs
$\mathcal{D}\langle i\rangle,\mathcal{D}\langle j\rangle$ with
$i<\frac{k+1}{2}$ and $j>\frac{k+1}{2}$, adding it to the coefficient of the
appropriate $\mathcal{D}_{i,j}$) until $\mathcal{D}$ vanishes (i.e.,
$\mathcal{D}\langle i\rangle$ is zero for all $i\in\\{0\\}\cup[k]$).
Similarly, every distribution $\mathcal{D}\in\Delta_{k}^{-}$ can be
represented as a convex combination of the distributions
$\\{\mathcal{D}_{i}\\}_{i\geq\frac{k+1}{2}}\cup\\{\mathcal{D}_{i,j}\\}$. Thus,
by Proposition 4.5, it is sufficient to verify that

$\frac{\lambda_{\\{\frac{k+1}{2}\\}}(\mathcal{D},p)}{\gamma_{\\{\frac{k+1}{2}\\},k}(\mu(\mathcal{D}))}\geq\frac{\lambda_{\\{\frac{k+1}{2}\\}}(\mathcal{D}_{N}^{*},p)}{\gamma_{\\{\frac{k+1}{2}\\},k}(\mu(\mathcal{D}_{N}^{*}))}$

for each $\mathcal{D}\in\\{\mathcal{D}_{i}\\}\cup\\{\mathcal{D}_{i,j}\\}$.
Treating $p$ as a variable, for each odd $k\in\\{3,\ldots,51\\}$ we produce a
list of $O(k^{2})$ degree-$k$ polynomial inequalities in $p$ which we verify
using Mathematica. ∎

###  5.3 More symmetric functions

In Table 1 below, we list four more symmetric Boolean functions (beyond
$k\textsf{AND}$, $\mathsf{Th}^{k-1}_{k}$, and $\mathsf{Ex}^{(k+1)/2}_{k}$)
whose sketching approximability we have analytically resolved using the “max-
min method”. These values were calculated using two functions in the
Mathematica code, estimateAlpha — which numerically or symbolically estimates
the $\mathcal{D}_{N}$, with a given support, which minimizes $\alpha$ — and
testMinMax — which, given a particular $\mathcal{D}_{N}$, calculates $p^{*}$
for that $\mathcal{D}_{N}$ and checks analytically whether lower-bounding by
evaluating $\lambda_{S}$ at $p^{*}$ proves that $\mathcal{D}_{N}$ is minimal.

$S$ | $k$ | $\alpha$ | $\mathcal{D}_{N}^{*}$
---|---|---|---
$\\{2,3\\}$ | $3$ | $\frac{1}{2}+\frac{\sqrt{3}}{18}\approx 0.5962$ | $(0,\frac{1}{2},0,\frac{1}{2})$
$\\{4,5\\}$ | $5$ | $8\operatorname{root}_{\mathbb{R}}(P_{1})\approx 0.2831$ | $(0,0,1-\operatorname{root}_{\mathbb{R}}(P_{2}),\operatorname{root}_{\mathbb{R}}(P_{2}),0,0)$
$\\{4\\}$ | $5$ | $8\operatorname{root}_{\mathbb{R}}(P_{3})\approx 0.2394$ | $(0,0,1-\operatorname{root}_{\mathbb{R}}(P_{4}),\operatorname{root}_{\mathbb{R}}(P_{4}),0,0)$
$\\{3,4,5\\}$ | $5$ | $\frac{1}{2}+\frac{3\sqrt{5}}{125}\approx 0.5537$ | $(0,\frac{1}{2},0,0,0,\frac{1}{2})$
Table 1: Symmetric functions for which we have analytically calculated exact
$\alpha$ values using the “max-min method”. For a polynomial
$P:\mathbb{R}\to\mathbb{R}$ with a _unique_ positive real root, let
$\operatorname{root}_{\mathbb{R}}(p)$ denote that root, and define the
polynomials
$P_{1}(z)=-72+4890z-108999z^{2}+800000z^{3},P_{2}(z)=-908+5021z-9001z^{2}+5158z^{3}$,
$P_{3}(z)=-60+5745z-183426z^{2}+1953125z^{3}$,
$P_{4}(z)=-344+1770z-3102z^{2}+1811z^{3}$. (We note that in the
$f_{\\{4\\},5}$ and $f_{\\{4,5\\},5}$ calculations, we were required to check
equality of roots numerically (to high precision) instead of analytically).

We remark that two of the cases in Table 1 (as well as $k\textsf{AND}$), the
optimal $\mathcal{D}_{N}$ is rational and supported on two coordinates.
However, in the other two cases in Table 1, the optimal $\mathcal{D}_{N}$
involves roots of a cubic.

In Section 5.2, we showed that $\mathcal{D}_{N}^{*}$ defined by
$\mathcal{D}_{N}^{*}\langle 0\rangle=\frac{k-1}{2k}$ and
$\mathcal{D}_{N}^{*}\langle k\rangle=\frac{k+1}{2k}$ is optimal for
$\mathsf{Ex}^{(k+1)/2}_{k}$ for odd $k\in\\{3,\ldots,51\\}$. Using the same
$\mathcal{D}_{N}^{*}$, we are also able to resolve 11 other cases in which $S$
is “close to” $\\{\frac{k+1}{2}\\}$; for instance,
$S=\\{5,6\\},\\{5,6,7\\},\\{5,7\\}$ for $k=9$. (We have omitted the values of
$\alpha$ and $\mathcal{D}_{N}$ because they are defined using the roots of
polynomials of degree up to 8.)

In all previously-mentioned cases, the condition “$\mathcal{D}_{N}^{*}$ has
support size $2$” was helpful, as it makes the optimization problem over
$\mathcal{D}_{N}^{*}$ essentially univariate; however, we have confirmed
analytically in two other cases ($S=\\{3\\},k=4$ and $S=\\{3,5\\},k=5$) that
“max-min method on distributions with support size two” does not suffice for
tight bounds on $\alpha$ (see testDistsWithSupportSize2 in the Mathematica
code). However, using the max-min method with $\mathcal{D}_{N}$ supported on
two levels still achieves decent (but not tight) bounds on $\alpha$. For
$S=\\{3\\},k=4$, using $\mathcal{D}_{N}=(\frac{1}{4},0,0,0,\frac{3}{4})$, we
get the bounds $\alpha(f_{\\{3\\},4})\in[0.3209,0.3295]$ (the difference being
$2.67\%$). For $S=\\{3,5\\},k=5$, using
$\mathcal{D}_{N}=(\frac{1}{4},0,0,0,\frac{3}{4},0)$, we get
$\alpha(f_{\\{3,5\\},5})\in[0.3416,0.3635]$ (the difference being $6.42\%$).

Finally, we have also analyzed cases where we get numerical solutions which
are very close to tight, but we lack analytical solutions because they likely
involve roots of high-degree polynomials. For instance, in the case
$S=\\{4,5,6\\},k=6$, setting $\mathcal{D}_{N}=(0,0,0,0.930013,0,0,0.069987)$
gives $\alpha(f_{\\{4,5,6\\},6})\in[0.44409972,0.44409973]$, differing only by
0.000003%. (We conjecture here that $\alpha=\frac{4}{9}$.) For
$S=\\{6,7,8\\},k=8$, using $\mathcal{D}_{N}=(0,0,0,0,0.699501,0.300499)$, we
get the bounds $\alpha(f_{\\{6,7,8\\},8})\in[0.20848,0.20854]$ (the difference
being $0.02\%$).777Interestingly, in this latter case, we get bounds differing
by $2.12\%$ using $\mathcal{D}_{N}=(0,0,0,0,\frac{9}{13},\frac{4}{13},0,0,0)$
in an attempt to continue the pattern from $f_{\\{7,8\\},8}$ and
$f_{\\{8\\},8}$ (where we set
$\mathcal{D}_{N}^{*}=(0,0,0,0,\frac{16}{25},\frac{9}{25},0,0,0)$ and
$(0,0,0,0,\frac{25}{41},\frac{16}{41},0,0,0)$ in Section 5.1 and Section 4,
respectively).

##  6 Incompleteness of streaming lower bounds: Proving Theorem 2.12

In this section, we prove Theorem 2.12, showing that the streaming lower
bounds from [CGSV21] (Theorem 2.11) cannot characterize the _streaming_
approximability of $3$AND.

######  Lemma 6.1.

For $\mathcal{D}\in\Delta_{3}$, the expression

$\frac{\lambda_{\\{3\\}}(\mathcal{D},\frac{1}{3}\mathcal{D}\langle
1\rangle+\frac{2}{3}\mathcal{D}\langle 2\rangle+\mathcal{D}\langle
3\rangle)}{\gamma_{\\{3\\},3}(\mu(\mathcal{D}))}$

is minimized uniquely at $\mathcal{D}=(0,0,1,0)$, with value $\frac{2}{9}$.

###### Proof.

Letting $p=\frac{1}{3}\mathcal{D}\langle
1\rangle+\frac{2}{3}\mathcal{D}\langle 2\rangle+\mathcal{D}\langle 3\rangle$
and $q=1-p$, by Lemmas 3.2, 3.3 and 3.1 the expression expands to

$\frac{\mathcal{D}\langle 0\rangle\,p^{3}+\mathcal{D}\langle
1\rangle\,p^{2}(1-p)+\mathcal{D}\langle
2\rangle\,p(1-p)^{2}+\mathcal{D}\langle
3\rangle\,(1-p)^{3}}{\frac{1}{2}(1-\mathcal{D}\langle
0\rangle-\frac{1}{3}\mathcal{D}\langle 1\rangle+\frac{1}{3}\mathcal{D}\langle
2\rangle+\mathcal{D}\langle 3\rangle)}.$

The expression’s minimum, and its uniqueness, are confirmed analytically in
the Mathematica code. ∎

######  Lemma 6.2.

Let $X$ be a compact topological space, $Y\subseteq X$ a closed subspace, $Z$
a topological space, and $f:X\to Z$ a continuous map. Let $x^{*}\in X,z^{*}\in
Z$ be such that $f^{-1}(z^{*})=\\{x^{*}\\}$. Let
$\\{x_{i}\\}_{i\in\mathbb{N}}$ be a sequence of points in $Y$ such that
$\\{f(x_{i})\\}_{i\in\mathbb{N}}$ converges to $z^{*}$. Then $x^{*}\in Y$.

###### Proof.

By compactness of $X$, there is a subsequence
$\\{x_{j_{i}}\\}_{i\in\mathbb{N}}$ which converges to a limit $\widetilde{x}$.
By closure, $\widetilde{x}\in Y$. By continuity, $f(\widetilde{x})=z^{*}$, so
$\widetilde{x}=x^{*}$. ∎

Finally, we have:

###### Proof of Theorem 2.12.

By Lemma 6.1,
$\frac{\beta_{\\{3\\}}(\mathcal{D}_{N})}{\gamma_{\\{3\\},3}(\mu(\mathcal{D}_{N}))}$
is minimized _uniquely_ at $\mathcal{D}_{N}^{*}=(0,0,1,0)$. By Lemma 3.1 we
have $\mu(\mathcal{D}_{N}^{*})=\frac{1}{3}$, and by inspection from the proof
of Lemma 3.3 below, $\gamma_{\\{3\\}}(\mathcal{D}_{Y})$ with
$\mu(\mathcal{D}_{Y})=\frac{1}{3}$ is uniquely minimized by
$\mathcal{D}_{Y}^{*}=(\frac{1}{3},0,0,\frac{2}{3})$.

Finally, we rule out the possibility of an infinite sequence of padded one-
wise pairs which achieve ratios arbitrarily close to $\frac{2}{9}$ using
topological properties. View a distribution $\mathcal{D}\in\Delta_{3}$ as the
vector $(\mathcal{D}\langle 0\rangle,\mathcal{D}\langle
1\rangle,\mathcal{D}\langle 2\rangle,\mathcal{D}\langle
3\rangle)\in\mathbb{R}^{4}$. Let $D\subset\mathbb{R}^{4}$ denote the set of
such distributions. Let $M\subset D\times D\subset\mathbb{R}^{8}$ denote the
subset of pairs of distributions with matching marginals, and let
$M^{\prime}\subset M$ denote the subset of pairs with uniform marginals and
$P\subset M$ the subset of padded one-wise pairs. $D$, $M$, $M^{\prime}$, and
$P$ are compact (under the Euclidean topology); indeed, $D$, $M$, and
$M^{\prime}$ are bounded and defined by a finite collection of linear
equalities and strict inequalities, and letting $M^{\prime}\subset M$ denote
the subset of pairs of distributions with matching _uniform_ marginals, $P$ is
the image of the compact set $[0,1]\times D\times
M^{\prime}\subset\mathbb{R}^{13}$ under the continuous map
$\tau\times\mathcal{D}_{0}\times(\mathcal{D}^{\prime}_{Y},\mathcal{D}^{\prime}_{N})\mapsto(\tau\mathcal{D}_{0}+(1-\tau)\mathcal{D}^{\prime}_{Y},\tau\mathcal{D}_{0}+(1-\tau)\mathcal{D}^{\prime}_{N})$.
Hence, $P$ is closed.

Now the function

$\alpha:M\to\mathbb{R}\cup\\{\infty\\}:(\mathcal{D}_{N},\mathcal{D}_{Y})\mapsto\frac{\beta_{\\{3\\}}(\mathcal{D}_{N})}{\gamma_{\\{3\\}}(\mathcal{D}_{Y})}$

is continuous, since a ratio of continuous functions is continuous, and
$\beta_{\\{3\\}}$ is a single-variable supremum of a continuous function
(i.e., $\lambda_{S}$) over a compact interval, which is in general continuous
in the remaining variables. Thus, if there were a sequence of padded one-wise
pairs $\\{(\mathcal{D}_{N}^{(i)},\mathcal{D}_{Y}^{(i)})\in
P\\}_{i\in\mathbb{N}}$ such that
$\alpha(\mathcal{D}_{N}^{(i)},\mathcal{D}_{Y}^{(i)})$ converges to
$\frac{2}{9}$ as $i\to\infty$, since $M$ is compact and $P$ is closed, Lemmas
6.2 and 6.1 imply that $(\mathcal{D}_{N}^{*},\mathcal{D}_{Y}^{*})\in P$, a
contradiction. ∎

##  7 Simple sketching algorithms for threshold functions

The main goal of this section is to prove Theorem 1.7, giving a simple “bias-
based” sketching algorithm for threshold functions $\mathsf{Th}^{i}_{k}$.
Given an instance $\Psi$ of $\textsf{Max-CSP}(\mathsf{Th}^{i}_{k})$, for
$i\in[n]$, let $\mathsf{diff}_{i}(\Psi)$ denote the total weight of clauses in
which $x_{i}$ appears positively minus the weight of those in which it appears
negatively; that is, if $\Psi$ consists of clauses
$(\mathbf{b}(1),\mathbf{j}(1)),\ldots,(\mathbf{b}(m),\mathbf{j}(m))$ with
weights $w_{1},\ldots,w_{m}$, then

$\mathsf{diff}_{i}(\Psi)\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\sum_{\ell\in[m]\text{ s.t. }j(\ell)_{t}=i\text{ for some
}t\in[k]}b(\ell)_{t}w_{\ell}.$

Let $\textsf{bias}(\Psi)\stackrel{{\scriptstyle\mathrm{\small
def}}}{{=}}\frac{1}{kW}\sum_{i=1}^{n}|\mathsf{diff}_{i}(\Psi)|$, where
$W=\sum_{\ell=1}^{m}w_{\ell}$ is the total weight in $\Psi$.

Let $S=\\{i,\ldots,k\\}$ so that $\mathsf{Th}^{i}_{k}=f_{S,k}$. Recall the
definitions of $\beta_{S,k}(\mu)$ and $\gamma_{S,k}(\mu)$ from Eq. 2.7. Our
simple algorithm for $\textsf{Max-CSP}(\mathsf{Th}^{i}_{k})$ relies on the
following two lemmas, which we prove below:

######  Lemma 7.1.

$\textsf{val}_{\Psi}\leq\gamma_{S,k}(\textsf{bias}(\Psi))$.

######  Lemma 7.2.

$\textsf{val}_{\Psi}\geq\beta_{S,k}(\textsf{bias}(\Psi))$.

Together, these two lemmas imply that outputting
$\alpha(\mathsf{Th}^{i}_{k})\cdot\gamma_{S,k}(\textsf{bias}(\Psi))$ gives an
$\alpha(\mathsf{Th}^{i}_{k})$-approximation to $\textsf{Max-
CSP}(\mathsf{Th}^{i}_{k})$, since
$\alpha(\mathsf{Th}^{i}_{k})=\inf_{\mu\in[-1,1]}\frac{\beta_{S,k}(\mu)}{\gamma_{S,k}(\mu)}$
(Eq. 2.7). We can implement this as a small-space sketching algorithm (up to
an arbitrarily small constant $\epsilon>0$ in the approximation ratio) because
$\textsf{bias}(\Psi)$ is measurable using $\ell_{1}$-sketching algorithms (as
used also in [GVV17, CGV20, CGSV21]) and $\gamma_{S,k}(\cdot)$ is piecewise
linear:

######  Theorem 7.3 ([Ind06, KNW10]).

For every $\epsilon>0$, there exists an $O(\log n/\epsilon^{2})$-space
randomized sketching algorithm for the following problem: The input is a
stream $S$ of updates of the form
$(i,v)\in[n]\times\\{-\mathrm{poly}(n),\ldots,\mathrm{poly}(n)\\}$, and the
goal is to estimate the $\ell_{1}$-norm of the vector $x\in[n]^{n}$ defined by
$x_{i}=\sum_{(i,v)\in S}v$, up to a multiplicative factor of $1\pm\epsilon$.

######  Corollary 7.4.

For $f:\\{-1,1\\}^{k}\to\\{0,1\\}$ and every $\epsilon>0$, there exists an
$O(\log n/\epsilon^{2})$-space randomized sketching algorithm for the
following problem: The input is an instance $\Psi$ of $\textsf{Max-
CSP}(\mathsf{Th}^{i}_{k})$ (given as a stream of constraints), and the goal is
to estimate $\textsf{bias}(\Psi)$ up to a multiplicative factor of
$1\pm\epsilon$.

###### Proof.

Invoke the $\ell_{1}$-norm sketching algorithm from Theorem 7.3 as follows: On
each input constraint
$(\mathbf{b}=(b_{1},\ldots,b_{k}),\mathbf{j}=(j_{1},\ldots,j_{k}))$ with
weight $w$, insert the updates $(j_{1},wb_{1}),\ldots,(j_{k},wb_{k})$ into the
stream (and normalize appropriately). ∎

Theorem 1.7 then follows from Lemmas 7.2, 7.1 and 7.4; we include a formal
proof in Appendix A for completeness.

To prove Lemmas 7.2 and 7.1, we require a bit more setup. Adapting notation
from [CGSV21, §4.2], given an instance $\Psi$ of $\textsf{Max-
CSP}(\mathsf{Th}^{i}_{k})$ and a “negation pattern”
$\mathbf{a}=(a_{1},\ldots,a_{n})\in\\{-1,1\\}^{n}$ for the variables, let
$\Psi^{\mathbf{a}}$ be the instance which results from $\Psi$ by “flipping”
the variables according to $\mathbf{a}$ (formally, each constraint
$(\mathbf{b},\mathbf{j})$ is replaced with
$(\mathbf{b}\odot\mathbf{a}|_{\mathbf{j}},\mathbf{j})$). We summarize the
useful properties of this operation in the following claim:

######  Proposition 7.5.

Let $\Psi$ be an instance of $\textsf{Max-CSP}(\mathsf{Th}^{i}_{k})$ and
$\mathbf{a}=(a_{1},\ldots,a_{n})\in\\{-1,1\\}^{n}$. Then:

  1. i.

For each $i\in[n]$,
$\mathsf{diff}_{i}(\Psi^{\mathbf{a}})=a_{i}\mathsf{diff}_{i}(\Psi)$.

  2. ii.

$\textsf{bias}(\Psi)=\textsf{bias}(\Psi^{\mathbf{a}})$.

  3. iii.

For any $\bm{\sigma}\in\\{-1,1\\}^{n}$,
$\textsf{val}_{\Psi^{\mathbf{a}}}(\bm{\sigma})=\textsf{val}_{\Psi}(\mathbf{a}\odot\bm{\sigma})$.

  4. iv.

$\textsf{val}_{\Psi^{\mathbf{a}}}=\textsf{val}_{\Psi}$.

###### Proof.

For Item i, we have

$\displaystyle\mathsf{diff}_{i}(\Psi^{\mathbf{a}})$
$\displaystyle=\sum_{\ell\in[m]\text{ s.t. }j(\ell)_{t}=i\text{ for some
}t\in[k]}a_{j(\ell)_{t}}b(\ell)_{t}w_{\ell}$ (definition of
$\mathsf{diff}_{i}$) $\displaystyle=a_{i}\;\sum_{\ell\in[m]\text{ s.t.
}j(\ell)_{t}=i\text{ for some }t\in[k]}b(\ell)_{t}w_{\ell}$
$\displaystyle=a_{i}\mathsf{diff}_{i}(\Psi).$ (definition of
$\mathsf{diff}_{i}$)

Item ii follows immediately from Item i and the definition
$\textsf{bias}(\Psi)=\frac{1}{kW}\sum_{i=1}^{n}|\mathsf{diff}_{i}(\Psi)|$. For
Item iii, we have

$\displaystyle\textsf{val}_{\Psi^{\mathbf{a}}}(\bm{\sigma})$
$\displaystyle=\frac{1}{W}\sum_{i\in[m]}w_{i}\mathsf{Th}^{i}_{k}((\mathbf{b}(i)\odot\mathbf{a}|_{\mathbf{j}(i)})\odot\bm{\sigma}|_{\mathbf{j}(i)})$
(definitions of $\Psi^{\mathbf{a}}$ and val)
$\displaystyle=\frac{1}{W}\sum_{i\in[m]}w_{i}\mathsf{Th}^{i}_{k}(\mathbf{b}(i)\odot(\bm{\sigma}\odot\mathbf{a})|_{\mathbf{j}(i)})$
$\displaystyle=\textsf{val}_{\Psi}(\bm{\sigma}\odot\mathbf{a}).$ (definition
of val)

Finally, Item iv follows from Item iii and the fact that
$\\{\bm{\sigma}:\bm{\sigma}\in\\{-1,1\\}^{n}\\}=\\{\bm{\sigma}\odot\mathbf{a}:\bm{\sigma}\in\\{-1,1\\}^{n}\\}$:

$\textsf{val}_{\Psi^{\mathbf{a}}}=\max_{\bm{\sigma}\in\\{-1,1\\}^{n}}\textsf{val}_{\Psi^{\mathbf{a}}}(\bm{\sigma})=\max_{\bm{\sigma}\in\\{-1,1\\}^{n}}\textsf{val}_{\Psi}(\bm{\sigma}\odot\mathbf{a})=\max_{\bm{\sigma}\in\\{-1,1\\}^{n}}\textsf{val}_{\Psi}(\bm{\sigma})=\textsf{val}_{\Psi}.$

∎

Also, given an instance $\Psi$, we define its “symmetrized canonical
distribution” $\mathcal{D}^{\mathrm{sym}}_{\Psi}\in\Delta_{k}$ to be the
distribution obtained by sampling a constraint at random from $\Psi$ and
outputting its “randomly permuted negation pattern”. Formally, let
$\mathsf{S}_{k}$ denote the set of permutations $[k]\to[k]$. For a vector
$\mathbf{b}=(b_{1},\ldots,b_{k})\in\\{-1,1\\}^{k}$ and a permutation
$\bm{\pi}\in\mathsf{S}_{k}$, let
$\bm{\pi}(\mathbf{b})=(b_{\bm{\pi}(1)},\ldots,b_{\bm{\pi}(k)})$. Let
$C(i)=(\mathbf{b}(i),\mathbf{j}(i))$ denote the $i$-th constraint of $\Psi$,
with weight $w_{i}$, and let $W=\sum_{i=1}^{m}w_{i}$ be the total weight. To
sample a random vector from $\mathcal{D}^{\mathrm{sym}}_{\Psi}$, we sample
$i\in[m]$ with probability $w_{i}/W$, sample a permutation
$\bm{\pi}\sim\mathsf{Unif}(\mathsf{S}_{k})$, and output
$\bm{\pi}(\mathbf{b}(i))$. The useful properties of
$\mathcal{D}^{\mathrm{sym}}_{\Psi}$ are summarized in the following claim:

######  Proposition 7.6.

Let $\Psi$ be an instance of $\textsf{Max-CSP}(\mathsf{Th}^{i}_{k})$. Then:

  1. i.

For any $p\in[0,1]$,
$\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p)^{n}}[\textsf{val}_{\Psi}(\mathbf{a})]=\lambda_{S}(\mathcal{D}^{\mathrm{sym}}_{\Psi},p)$.

  2. ii.

$\mu(\mathcal{D}^{\mathrm{sym}}_{\Psi})=\frac{1}{kW}\sum_{i=1}^{n}\mathsf{diff}_{i}(\Psi)\leq\textsf{bias}(\Psi)$.

  3. iii.

If $\mathsf{diff}_{i}(\Psi)\geq 0$ for all $i\in[n]$, then
$\mu(\mathcal{D}^{\mathrm{sym}}_{\Psi})=\textsf{bias}(\Psi)$.

###### Proof.

We begin with Item i. Fix a constraint $(\mathbf{b},\mathbf{j})$. We make two
observations. Firstly, if we sample $\mathbf{a}\sim\mathsf{Bern}(p)^{n}$, the
distribution of $\mathbf{a}|_{\mathbf{j}}$ is identical to
$\mathsf{Bern}(p)^{k}$. Secondly, for a fixed vector
$\mathbf{b}\in\\{-1,1\\}^{k}$, if we sample
$\mathbf{a}\sim\mathsf{Bern}(p)^{k}$ and
$\bm{\pi}\sim\mathsf{Unif}(\mathsf{S}_{k})$, the distributions of
$\bm{\pi}(\mathbf{b})\odot\mathbf{a}$ and
$\bm{\pi}(\mathbf{b}\odot\mathbf{a})$ are identical. Thus, we have

$\displaystyle\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p)^{n}}[\mathsf{Th}^{i}_{k}(\mathbf{b}(i)\odot\mathbf{a}|_{\mathbf{j}})]$
$\displaystyle=\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p)^{k}}[\mathsf{Th}^{i}_{k}(\mathbf{b}\odot\mathbf{a})]$
(first observation)
$\displaystyle=\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p)^{k},\bm{\pi}\sim\mathsf{Unif}(\mathsf{S}_{k})}[\mathsf{Th}^{i}_{k}(\bm{\pi}(\mathbf{b}\odot\mathbf{a}))]$
(symmetry of $\mathsf{Th}^{i}_{k}$)
$\displaystyle=\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p)^{k},\bm{\pi}\sim\mathsf{Unif}(\mathsf{S}_{k})}[\mathsf{Th}^{i}_{k}(\bm{\pi}(\mathbf{b})\odot\mathbf{a})].$
(second observation)

Thus, by linearity of expectation, we have
$\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p)^{n}}[\textsf{val}_{\Psi}(\mathbf{a})]=\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p)^{k},\mathbf{b}\sim\mathcal{D}^{\mathrm{sym}}_{\Psi}}[\mathsf{Th}^{i}_{k}(\mathbf{b}\odot\mathbf{a})]=\lambda_{S}(\mathcal{D}^{\mathrm{sym}}_{\Psi},p)$,
as desired.

For Item ii, we have

$\displaystyle\frac{1}{kW}\sum_{i=1}^{n}\mathsf{diff}_{i}(\Psi)$
$\displaystyle=\frac{1}{kW}\sum_{\ell=1}^{m}w_{\ell}\sum_{t=1}^{k}b(\ell)_{t}$
(definition of $\mathsf{diff}_{i}(\Psi)$)
$\displaystyle=\frac{1}{W}\sum_{\ell=1}^{m}w_{\ell}\mathop{\mathbb{E}}_{\bm{\pi}\sim\mathsf{S}_{k}}[\pi(\mathbf{b})_{1}]$
(where
$\bm{\pi}(\mathbf{b})=(\pi(\mathbf{b})_{1},\ldots,\pi(\mathbf{b})_{k})$)
$\displaystyle=\mathop{\mathbb{E}}_{\mathbf{b}\sim\mathcal{D}^{\mathrm{sym}}_{\Psi}}[b_{1}]$
(definition of $\mathcal{D}^{\mathrm{sym}}_{\Psi}$)
$\displaystyle=\mu(\mathcal{D}^{\mathrm{sym}}_{\Psi}).$ (definition of $\mu$)

Finally, Item iii follows immediately from Item ii and the definition
$\textsf{bias}(\Psi)=\frac{1}{kW}\sum_{i=1}^{n}|\mathsf{diff}_{i}(\Psi)|$. ∎

Now, we are equipped to prove the lemmas:

###### Proof of Lemma 7.1.

Let $\mathbf{opt}\in\\{-1,1\\}^{n}$ denote the optimal assignment for $\Psi$.
Then

$\displaystyle\textsf{val}_{\Psi}$
$\displaystyle=\textsf{val}_{\Psi}(\mathbf{opt})$ (definition of
$\mathbf{opt}$) $\displaystyle=\textsf{val}_{\Psi^{\mathbf{opt}}}(1^{n})$
(Item iii of Proposition 7.5)
$\displaystyle=\lambda_{S}(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{opt}}},1)$
(Item i of Proposition 7.6 with $p=1$)
$\displaystyle=\gamma_{S}(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{opt}}})$
(definition of $\gamma_{S}$, Eq. 2.3)
$\displaystyle\leq\gamma_{S,k}(\mu(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{opt}}}))$
(definition of $\gamma_{S,k}$, Eq. 2.6)
$\displaystyle\leq\gamma_{S,k}(\textsf{bias}(\Psi^{\mathbf{opt}}))$ (Item ii
of Proposition 7.6 and monotonicity of $\gamma_{S,k}$)
$\displaystyle=\gamma_{S,k}(\textsf{bias}(\Psi)),$ (Item ii of Proposition
7.5)

as desired. ∎

###### Proof of Lemma 7.2.

Let $\mathbf{maj}\in\\{-1,1\\}^{n}$ denote the assignment assigning $x_{i}$ to
$1$ if $\mathsf{diff}_{i}(\Psi)\geq 0$ and $-1$ otherwise. Now

$\displaystyle\textsf{val}_{\Psi}$
$\displaystyle=\textsf{val}_{\Psi^{\mathbf{maj}}}$ (Item iv of Proposition
7.5)
$\displaystyle\geq\sup_{p\in[0,1]}\left(\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p)^{n}}[\textsf{val}_{\Psi^{\mathbf{maj}}}(\mathbf{a})]\right)$
(probabilistic method)
$\displaystyle=\sup_{p\in[0,1]}(\lambda_{S}(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{maj}}},p))$
(Item i of Proposition 7.6)
$\displaystyle\geq\beta_{S}(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{maj}}})$
(definition of $\beta_{S}$, Eq. 2.3)
$\displaystyle\geq\beta_{S,k}(\mu(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{maj}}}))$
(definition of $\beta_{S,k}$, Eq. 2.6)
$\displaystyle=\beta_{S,k}(\textsf{bias}(\Psi^{\mathbf{maj}}))$ (Item iii of
Proposition 7.6) $\displaystyle=\beta_{S,k}(\textsf{bias}(\Psi)),$ (Item ii of
Proposition 7.5)

as desired. ∎

Finally, we state another consequence of Lemma 7.1 — a simple randomized,
$O(n)$-time-and-space streaming algorithm for _outputting_ approximately-
optimal assignments when the max-min method applies.

######  Theorem 7.7.

Let $\mathsf{Th}^{i}_{k}$ be a threshold function and $p^{*}\in[0,1]$ be such
that the max-min method applies, i.e.,

$\alpha(\mathsf{Th}^{i}_{k})=\inf_{\mathcal{D}_{N}\in\Delta_{k}}\left(\frac{\lambda_{S}(\mathcal{D}_{N},p^{*})}{\gamma_{S,k}(\mu(\mathcal{D}_{N}))}\right).$

Then the following algorithm, on input $\Psi$, outputs an assignment with
expected value at least $\alpha(\mathsf{Th}^{i}_{k})\cdot\textsf{val}_{\Psi}$:
Assign every variable to $1$ if $\mathsf{diff}_{i}(\Psi)\geq 0$, and $-1$
otherwise, and then flip each variable’s assignment independently with
probability $p^{*}$.

###### Proof.

Let $p^{*}$ be as in the theorem statement, and define $\mathbf{maj}$ as in
the proof of Lemma 7.2. We output the assignment $\mathbf{maj}\odot\mathbf{a}$
for $\mathbf{a}\sim\mathsf{Bern}(p^{*})^{n}$, and our goal is to show that its
expected value is at least $\alpha(\mathsf{Th}^{i}_{k})\textsf{val}_{\Psi}$.

Our assumption that the max-min method applies asserts in particular that

$\lambda_{S}(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{maj}}},p^{*})\geq\alpha(\mathsf{Th}^{i}_{k})\gamma_{S,k}(\mu(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{maj}}})).$
(7.8)

Thus our expected output value is

$\displaystyle\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p^{*})}[\textsf{val}_{\Psi}(\mathbf{maj}\odot\mathbf{a})]$
$\displaystyle=\mathop{\mathbb{E}}_{\mathbf{a}\sim\mathsf{Bern}(p^{*})}[\textsf{val}_{\Psi^{\mathbf{maj}}}(\mathbf{a})]$
(Item iii of Proposition 7.5)
$\displaystyle=\lambda_{S}(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{maj}}},p^{*})$
(Item i of Proposition 7.6)
$\displaystyle\geq\alpha(\mathsf{Th}^{i}_{k})\gamma_{S,k}(\mu(\mathcal{D}^{\mathrm{sym}}_{\Psi^{\mathbf{maj}}}))$
(Eq. 7.8)
$\displaystyle=\alpha(\mathsf{Th}^{i}_{k})\gamma_{S,k}(\textsf{bias}(\Psi))$
(Item iii of Proposition 7.6)
$\displaystyle\geq\alpha(\mathsf{Th}^{i}_{k})\textsf{val}_{\Psi},$ (Lemma 7.1)

as desired. ∎

## Discussion

In this paper, we introduce the max-min method and use it to resolve the
streaming approximability of a wide variety of symmetric Boolean CSPs
(including infinite families such as $\textsf{Max-}k\textsf{AND}$ for all $k$,
and $\mathsf{Th}_{k}^{k-1}$ for all even $k$). However, these techniques are
in a sense “ad hoc” since we use computer assistance to guess the optimal
solution for our optimization problem. We leave the question of whether the
max-min method can be applied to determine the sketching approximability for
all symmetric Boolean CSPs as an interesting open problem.

Separately, we also establish that the techniques developed in [CGSV21] are
not sufficient to characterize the _streaming_ approximability of all CSPs.
Indeed, we show that their streaming lower bound based on “padded one-wise
pairs” cannot match the approximation ratio of their optimal sketching
algorithm for Max-$3$AND. While we believe that no $o(\sqrt{n})$-space
streaming algorithm can beat their sketching algorithm for Max-$3$AND, proving
this will require new techniques.

## Acknowledgements

All authors of this paper are or were supervised by Madhu Sudan. We would like
to thank him for advice and guidance on both technical and organizational
aspects of this project, as well as for many helpful comments on earlier
drafts of this paper.

## References

  * [BR21] Arindam Biswas and Venkatesh Raman  “Sublinear-Space Approximation Algorithms for Max $r$-SAT”  In _Computing and Combinatorics_ 13025, LNCS  Springer, Cham, 2021, pp. 124–136
  * [BV04] Stephen Boyd and Lieven Vandenberghe  “Convex Optimization”  Cambridge University Press, 2004  DOI: 10.1017/CBO9780511804441
  * [CGS+22] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker and Santhoshini Velusamy  “Linear Space Streaming Lower Bounds for Approximating CSPs” To appear  In _Proceedings of the 54th Annual ACM Symposium on Theory of Computing_ , 2022
  * [CGSV21] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan and Santhoshini Velusamy  “Approximability of All Boolean CSPs with Linear Sketches”, 2021  arXiv:2102.12351v7 [cs.CC]
  * [CGSV21a] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan and Santhoshini Velusamy  “Approximability of All Finite CSPs with Linear Sketches”  In _Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science_ IEEE Computer Society, 2021  DOI: 10.1109/FOCS52979.2021.00117
  * [CGV20] Chi-Ning Chou, Alexander Golovnev and Santhoshini Velusamy  “Optimal Streaming Approximations for All Boolean Max-2CSPs and Max-$k$SAT”  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science_ IEEE Computer Society, 2020, pp. 330–341  DOI: 10.1109/FOCS46700.2020.00039
  * [CMM09] Moses Charikar, Konstantin Makarychev and Yury Makarychev  “Near-Optimal Algorithms for Maximum Constraint Satisfaction Problems” Conference version in SODA 2007  In _ACM Transactions on Algorithms_ 5.3 Association for Computing Machinery, 2009, pp. 1–14  DOI: 10.1145/1541885.1541893
  * [EH08] Lars Engebretsen and Jonas Holmerin  “More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP” Conference version in STACS 2005  In _Random Structures and Algorithms_ 33.4 Wiley, 2008, pp. 497–514  DOI: 10.1002/rsa.20226
  * [FG95] Uriel Feige and Michel X. Goemans  “Approximating the Value of Two Prover Proof Systems, with Applications to MAX 2SAT and MAX DICUT”  In _Proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems_ IEEE Computer Society, 1995, pp. 182–189  DOI: 10.1109/ISTCS.1995.377033
  * [GVV17] Venkatesan Guruswami, Ameya Velingker and Santhoshini Velusamy  “Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_ 81, LIPIcs  Schloss Dagstuhl — Leibniz-Zentrum für Informatik, 2017, pp. 8:1–8:19  DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.8
  * [GW95] Michel X. Goemans and David P. Williamson  “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming” Conference version in STOC 1994  In _Journal of the ACM_ 42.6, 1995, pp. 1115–1145  DOI: 10.1145/227683.227684
  * [Hås01] Johan Håstad  “Some Optimal Inapproximability Results”  In _Journal of the ACM_ 48.4 Association for Computing Machinery, 2001, pp. 798–859  DOI: 10.1145/502090.502098
  * [Has04] Gustav Hast  “Approximating Max $k$CSP Using Random Restrictions”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_ 3122, LNCS  Springer, 2004, pp. 151–162  DOI: 10.1007/978-3-540-27821-4˙14
  * [Has05] Gustav Hast  “Approximating Max $k$CSP – Outperforming a Random Assignment with Almost a Linear Factor”  In _Automata, Languages and Programming_ 3580, LNCS  Springer, 2005, pp. 956–968  DOI: 10.1007/11523468˙77
  * [Ind06] Piotr Indyk  “Stable Distributions, Pseudorandom Generators, Embeddings, and Data Stream Computation” Conference version in FOCS 2000  In _Journal of the ACM_ 53.3, 2006, pp. 307–323  DOI: 10.1145/1147954.1147955
  * [KKS15] Michael Kapralov, Sanjeev Khanna and Madhu Sudan  “Streaming Lower Bounds for Approximating MAX-CUT”  In _Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms_ Society for Industrial and Applied Mathematics, 2015, pp. 1263–1282  DOI: 10.1137/1.9781611973730.84
  * [KNW10] Daniel M. Kane, Jelani Nelson and David P. Woodruff  “On the Exact Space Complexity of Sketching and Streaming Small Norms”  In _Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms_ Society for Industrial and Applied Mathematics, 2010, pp. 1161–1178  DOI: 10.1137/1.9781611973075.93
  * [ST00] Alex Samorodnitsky and Luca Trevisan  “A PCP Characterization of NP with Optimal Amortized Query Complexity”  In _Proceedings of the 32nd Annual ACM Symposium on Theory of Computing_ Portland, Oregon, United States: Association for Computing Machinery, 2000, pp. 191–199  DOI: 10.1145/335305.335329
  * [ST09] Alex Samorodnitsky and Luca Trevisan  “Gowers Uniformity, Influence of Variables, and PCPs” Conference version in STOC 2006  In _SIAM Journal on Computing_ 39.1 Society for Industrial and Applied Mathematics, 2009, pp. 323–360  DOI: 10.1137/070681612
  * [ST98] Madhu Sudan and Luca Trevisan  “Probabilistically Checkable Proofs with Low Amortized Query Complexity”  In _Proceedings of the 39th Annual Symposium on Foundations of Computer Science_ IEEE Computer Society, 1998, pp. 18–27  DOI: 10.1109/SFCS.1998.743425
  * [Tre98] Luca Trevisan  “Parallel Approximation Algorithms by Positive Linear Programming”  In _Algorithmica_ 21.1, 1998, pp. 72–88  DOI: 10.1007/PL00009209
  * [Tre98a] Luca Trevisan  “Recycling Queries in PCPs and in Linearity Tests”  In _Proceedings of the 30th Annual ACM Symposium on Theory of Computing_ Association for Computing Machinery, 1998, pp. 299–308  DOI: 10.1145/276698.276769
  * [TSSW00] Luca Trevisan, Gregory B. Sorkin, Madhu Sudan and David P. Williamson  “Gadgets, Approximation, and Linear Programming” Conference version in FOCS 1996  In _SIAM Journal on Computing_ 29.6 Society for Industrial and Applied Mathematics, 2000, pp. 2074–2097  DOI: 10.1137/S0097539797328847
  * [Zwi98] Uri Zwick  “Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint”  In _Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms_ Association for Computing Machinery, 1998, pp. 201–210  DOI: 10.5555/314613.314701

##  Appendix A Miscellaneous technical proofs

###### Proof of Proposition 4.5.

Firstly, we show that it suffices WLOG to take the special case where $r=n$
and $\mathbf{y}(1),\ldots,\mathbf{y}(n)$ is the standard basis for
$\mathbb{R}^{n}$. Indeed, assume the special case and note that for a general
case, we can let
$\mathbf{a}^{\prime}=(\mathbf{a}\cdot\mathbf{y}(1),\ldots,\mathbf{a}\cdot\mathbf{y}(r))$,
$\mathbf{b}^{\prime}=(\mathbf{b}\cdot\mathbf{y}(1),\ldots,\mathbf{b}\cdot\mathbf{y}(r))$,
$\mathbf{x}^{\prime}=(x_{1},\ldots,x_{r})$, and let
$\mathbf{y}^{\prime}(1),\ldots,\mathbf{y}^{\prime}(r)$ be the standard basis
for $\mathbb{R}^{r}$. Then
$\mathbf{x}^{\prime}=\sum_{i=1}^{r}\alpha_{i}\mathbf{y}^{\prime}(i)$ and

$f(\mathbf{x})=\frac{\sum_{i=1}^{r}(\mathbf{a}\cdot\mathbf{y}(i))\alpha_{i}}{\sum_{i=1}^{r}(\mathbf{b}\cdot\mathbf{y}(i))\alpha_{i}}=\frac{\mathbf{a}^{\prime}\cdot\mathbf{x}^{\prime}}{\mathbf{b}^{\prime}\cdot\mathbf{x}^{\prime}}\geq\min_{i\in[r]}\frac{\mathbf{a}^{\prime}\cdot\mathbf{y}^{\prime}(i)}{\mathbf{b}^{\prime}\cdot\mathbf{y}^{\prime}(i)}=\min_{i\in[r]}\frac{\mathbf{a}\cdot\mathbf{y}(i)}{\mathbf{b}\cdot\mathbf{y}(i)}.$

Now we prove the special case: Assume $r=n$ and
$\mathbf{y}(1),\ldots,\mathbf{y}(n)$ is the standard basis for
$\mathbb{R}^{n}$. We have $f(\mathbf{y}(i))=\frac{a_{i}}{b_{i}}$. Assume WLOG
that $f(\mathbf{y}(1))=\min\\{f(\mathbf{y}(i)):i\in[n]\\}$, i.e.,
$\frac{a_{1}}{b_{1}}\leq\frac{a_{i}}{b_{i}}$ for all $i\in[n]$. Then
$a_{i}\geq\frac{a_{1}b_{i}}{b_{1}}$ for all $i\in[n]$, so

$\mathbf{a}\cdot\mathbf{x}\geq\sum_{i=1}^{n}\frac{a_{1}b_{i}}{b_{1}}\alpha_{i}=\frac{a_{1}}{b_{1}}(\mathbf{b}\cdot\mathbf{x}).$

Hence

$f(\mathbf{x})=\frac{\mathbf{a}\cdot\mathbf{x}}{\mathbf{b}\cdot\mathbf{x}}\geq\frac{a_{1}}{b_{1}}=f(\mathbf{y}(1)),$

as desired. ∎

###### Proof of Theorem 1.7.

To get an $(\alpha-\epsilon)$-approximation to $\textsf{val}_{\Psi}$, let
$\delta>0$ be small enough such that
$\frac{1-\delta}{1+\delta}\alpha(\mathsf{Th}^{i}_{k})\geq\alpha(\mathsf{Th}^{i}_{k})-\epsilon$.
We claim that calculating an estimate $\widehat{b}$ for $\textsf{bias}(\Psi)$
(using Corollary 7.4) up to a multiplicative $\delta$ factor and outputting
$\widehat{v}=\alpha(\mathsf{Th}^{i}_{k})\gamma_{S,k}(\frac{\widehat{b}}{1+\delta})$
is sufficient.

Indeed, suppose
$\widehat{b}\in[(1-\delta)\textsf{bias}(\Psi),(1+\delta)\textsf{bias}(\Psi)]$;
then
$\frac{\widehat{b}}{1+\delta}\in[\frac{1-\delta}{1+\delta}\textsf{bias}(\Psi),\textsf{bias}(\Psi)]$.
Now we observe

$\displaystyle\gamma_{S,k}\left(\frac{\widehat{b}}{1+\delta}\right)$
$\displaystyle\geq\gamma_{S,k}\left(\frac{1-\delta}{1+\delta}\textsf{bias}(\Psi)\right)$
(monotonicity of $\gamma_{S,k}$)
$\displaystyle=\min\left\\{\frac{1+\frac{1-\delta}{1+\delta}\textsf{bias}(\Psi)}{1+\epsilon_{s,k}},1\right\\}$
(Lemma 3.3)
$\displaystyle\geq\frac{1-\delta}{1+\delta}\min\left\\{\frac{1+\textsf{bias}(\Psi)}{1+\epsilon_{s,k}},1\right\\}$
($\delta>0$)
$\displaystyle=\frac{1-\delta}{1+\delta}\gamma_{S,k}(\textsf{bias}(\Psi)).$
(Lemma 3.3)

Then we conclude

$\displaystyle(\alpha(\mathsf{Th}^{i}_{k})-\epsilon)\textsf{val}_{\Psi}$
$\displaystyle\leq(\alpha(\mathsf{Th}^{i}_{k})-\epsilon)\gamma_{S,k}(\textsf{bias}(\Psi))$
(Lemma 7.1)
$\displaystyle\leq\alpha(\mathsf{Th}^{i}_{k})\cdot\frac{1-\delta}{1+\delta}\gamma_{S,k}(\textsf{bias}(\Psi))$
(assumption on $\delta$) $\displaystyle\leq\widehat{v}$ (our observation)
$\displaystyle\leq\alpha(\mathsf{Th}^{i}_{k})\gamma_{S,k}(\textsf{bias}(\Psi))$
(monotonicity of $\gamma_{S,k}$)
$\displaystyle\leq\beta_{S,k}(\textsf{bias}(\Psi))$ (Eq. 2.7)
$\displaystyle\leq\textsf{val}_{\Psi},$ (Lemma 7.2)

as desired. ∎