$\lVert\mathcal{B}_{t}\lVert_{2}\leq c_{2}\lVert{B}_{t}\lVert_{2}$, which
implies that $\lim_{t\rightarrow\infty}\mathcal{B}_{t}=0$. ∎

With the lemma above, we directly utilize
$\lim_{t\rightarrow\infty}\mathcal{B}_{t}=0$ in proving Theorem 3.4.

######  Lemma F.2.

Let $X_{t}=(x_{t}^{\top},y_{t}^{\top})^{\top}$, then there exists $t_{0}>0$,
such that when $t>t_{0}$, $\left\|X_{t}\right\|_{2}$ is monotonically non-
increasing. Moreover, $\exists c_{0}\geq 0,\
\lim_{t\to\infty}\left\|X_{t}\right\|_{2}=c_{0}$.

###### Proof.

First we prove that there exists $t_{0}$ such that when $t>t_{0}$,
$\lVert\mathcal{A}_{t}\lVert_{2}\leq 1$.

From the proof of Lemma A.2, we know that if
$\alpha=\gamma\leq\frac{1}{\sigma_{t}}$, where $\sigma_{t}$ is the maximal
singular value of payoff matrix $A_{t}$, then the discriminant in equation
(10) is satisfied, i.e., $\lVert\mathcal{A}_{t}\lVert_{2}\leq 1$. Here we
choose $\alpha=\gamma\leq\frac{1}{2\sigma}$, where $\sigma$ is the maximal
singular value of payoff matrix $A$. Because $A_{t}$ converges to $A$, we can
conclude that there exists $t_{0}$, such that when $t\geq t_{0}$,
$\sigma_{t}<2\sigma$. This implies that
$\alpha=\gamma\leq\frac{1}{2\sigma}<\frac{1}{\sigma_{t}}$, which means
$\lVert\mathcal{A}_{t}\lVert_{2}\leq 1$. Therefore we prove that here exists
$t_{0}$ such that when $t>t_{0}$, $\lVert X_{t}\lVert_{2}\leq\lVert
X_{t-1}\lVert_{2}$. For any $t>t_{0}$, we have

$\displaystyle\lVert X_{t}\lVert_{2}$
$\displaystyle=\lVert\mathcal{A}_{t-1}X_{t-1}\lVert_{2}$
$\displaystyle\leq\lVert\mathcal{A}_{t-1}\lVert_{2}\lVert X_{t-1}\lVert_{2}$
$\displaystyle\leq\lVert X_{t-1}\lVert_{2}.$

Therefore, we have that when $t>t_{0}$, $\lVert X_{t}\lVert_{2}$ is
monotonically non-increasing.

From the fact that $\lVert X_{t}\lVert_{2}$ is monotonically non-increasing
and no smaller than 0, we obtain $\exists c_{0}\geq 0,\
\lim_{t\to\infty}\left\|X_{t}\right\|_{2}=c_{0}$. ∎

In fact, the property that $\lVert X_{t}\lVert_{2}$ is monotonically non-
increasing is closely related to the iterative matrix of EG is normal, which
causes part of the difference between EG and OGDA or negative momentum method.

######  Lemma F.3.

Decompose ${\mathbb{R}}^{n+m}=V_{1}\oplus V_{2}$ where $V_{1}$ is the
eigenspace of eigenvalue $1$ of matrix $\mathcal{A}$, $V_{1}$ and $V_{2}$ are
mutually perpendicular. Define $\lambda=\max_{s\neq
1,s\in\text{Eigenvalue}\mathcal{A}}\left|{s}\right|$. Then if $v\in V_{2}$,
$\left\|\mathcal{A}v\right\|_{2}\leq\lambda\left\|v\right\|_{2}$.

###### Proof.

Let $W_{s}=\\{v\in{\mathbb{R}}^{n+m}\mid\mathcal{A}v=sv\\}$, that is $W_{s}$
is the eigenspace of eigenvalue $s$ of $\mathcal{A}$. Let $V_{1}=W_{1}$ and
$V_{2}=\oplus_{s\neq 1}W_{s}$. By $\mathcal{A}$ is normal, we have
${\mathbb{R}}^{n+m}=V_{1}\oplus V_{2}$. $V_{1}$ and $V_{2}$ are mutually
perpendicular.

Then we only need to prove if $v\in V_{2}$,
$\left\|\mathcal{A}v\right\|_{2}\leq\lambda\left\|v\right\|_{2}$. From Lemma
A.2, we know that $\lambda<1$. Because

$\displaystyle V_{2}=\oplus_{s\neq 1,s\in\text{Eigenvalue}\mathcal{A}}W_{s},$

$v$ can be decomposed as $v=\sum_{s\neq
1,s\in\text{Eigenvalue}\mathcal{A}}k_{s}w_{s}$, where $w_{s}\in W_{s}$,
$k_{s}$ is the coefficient and for different $s_{1}$ and $s_{2}$ which are
eigenvalues of $\mathcal{A}$, $w_{s_{1}}$ and $w_{s_{2}}$ are perpendicular.

Therefore $\left\|v\right\|_{2}^{2}=\sum_{s\neq
1,s\in\text{Eigenvalue}\mathcal{A}}k_{s}^{2}\left\|w_{s}\right\|_{2}^{2}$.
Then $\mathcal{A}v=\sum_{s\neq
1,s\in\text{Eigenvalue}\mathcal{A}}k_{s}\mathcal{A}w_{s}$, therefore we have

$\displaystyle\left\|\mathcal{A}v\right\|_{2}^{2}$ $\displaystyle=\sum_{s\neq
1,s\in\text{Eigenvalue}\mathcal{A}}k_{s}^{2}\left\|\mathcal{A}w_{s}\right\|_{2}^{2}$
$\displaystyle=\sum_{s\neq
1,s\in\text{Eigenvalue}\mathcal{A}}{\left|{s}\right|}^{2}k_{s}^{2}\left\|w_{s}\right\|_{2}^{2}$
$\displaystyle\leq\lambda^{2}\sum_{s\neq
1,s\in\text{Eigenvalue}\mathcal{A}}k_{s}^{2}\left\|w_{s}\right\|_{2}^{2}$
$\displaystyle=\lambda^{2}\left\|v\right\|_{2}^{2}$

which means that
$\left\|\mathcal{A}v\right\|_{2}\leq\lambda\left\|v\right\|_{2}$, this
complete the proof. ∎

Now we can decompose $X_{t}=v_{t}^{1}+v_{t}^{2}$ where $v_{t}^{1}\in V_{1}$
and $v_{t}^{2}\in V_{2}$. Similarly, we also decompose
$\mathcal{B}_{t}X_{t}=w_{t}^{1}+w_{t}^{2}$ where $w_{t}^{1}\in V_{1}$ and
$w_{t}^{2}\in V_{2}$.

######  Lemma F.4.

If $\lim_{t\to\infty}\left\|v_{t}^{2}\right\|_{2}=0$, then
$\lim_{t\to\infty}(A^{\top}x_{t},Ay_{t})=(\boldsymbol{0},\boldsymbol{0})$,
which implies that $\lim_{t\rightarrow\infty}\Delta_{t}=0$.

###### Proof.

Let $v_{t}^{1}=\left(\begin{array}[]{l}x_{t}^{1}\\\
y_{t}^{1}\end{array}\right)$, $v_{t}^{2}=\left(\begin{array}[]{l}x_{t}^{2}\\\
y_{t}^{2}\end{array}\right)$, then by $X_{t}=\left(\begin{array}[]{l}x_{t}\\\
y_{t}\end{array}\right)=v_{t}^{1}+v_{t}^{2}$, we have
$x_{t}=x_{t}^{1}+x_{t}^{2}$ and $y_{t}=y_{t}^{1}+y_{t}^{2}$. First, we prove
$A^{\top}x_{t}^{1}=0$ and $Ay_{t}^{1}=0$. By $v_{t}^{1}\in V_{1}$, we have

$\displaystyle\begin{bmatrix}I-\alpha\gamma AA^{\top}&-\alpha A\\\ \\\ \alpha
A^{\top}&I-\alpha\gamma A^{\top}A\end{bmatrix}\begin{bmatrix}x_{t}^{1}\\\ \\\
y_{t}^{1}\end{bmatrix}=\begin{bmatrix}x_{t}^{1}\\\ \\\ y_{t}^{1}\end{bmatrix}$

that is

$\displaystyle\begin{bmatrix}x_{t}^{1}-\alpha\gamma AA^{\top}x_{t}^{1}-\alpha
Ay_{t}^{1}\\\ \\\ \alpha A^{\top}x_{t}^{1}+y_{t}^{1}-\alpha\gamma
A^{\top}Ay_{t}^{1}\end{bmatrix}=\begin{bmatrix}x_{t}^{1}\\\ \\\
y_{t}^{1}\end{bmatrix}$ $\displaystyle\Longrightarrow$
$\displaystyle\begin{cases}-\gamma AA^{\top}x_{t}^{1}-Ay_{t}^{1}=0,\\\
A^{\top}x_{t}^{1}-\gamma A^{\top}Ay_{t}^{1}=0,\end{cases}$
$\displaystyle\Longrightarrow$
$\displaystyle\begin{cases}A^{\top}x_{t}^{1}=0,\\\ Ay_{t}^{1}=0,\end{cases}$

where the second double arrow symbols is due to $\gamma^{2}AA^{\top}+I$ is
invertible.

According to $A^{\top}x_{t}^{1}=0$ and $Ay_{t}^{1}=0$, we have

$\displaystyle\begin{bmatrix}A^{\top}x_{t}\\\
Ay_{t}\end{bmatrix}=\begin{bmatrix}A^{\top}&\\\ &A\end{bmatrix}X_{t}$
$\displaystyle=\begin{bmatrix}A^{\top}&\\\
&A\end{bmatrix}(v_{t}^{1}+v_{t}^{2})$
$\displaystyle=\begin{bmatrix}A^{\top}&\\\
&A\end{bmatrix}\begin{bmatrix}x_{t}^{1}\\\
y_{t}^{1}\end{bmatrix}+\begin{bmatrix}A^{\top}&\\\ &A\end{bmatrix}v_{t}^{2}$
$\displaystyle=\begin{bmatrix}A^{\top}x_{t}^{1}\\\
Ay_{t}^{1}\end{bmatrix}+\begin{bmatrix}A^{\top}&\\\ &A\end{bmatrix}v_{t}^{2}$
$\displaystyle=\begin{bmatrix}A^{\top}&\\\ &A\end{bmatrix}v_{t}^{2}.$

We can see that if $\lim_{t\to\infty}\left\|v_{t}^{2}\right\|_{2}=0$, then
$\lim_{t\to\infty}(A^{\top}x_{t},Ay_{t})=(0,0)$ . ∎

Now we are ready to prove Theorem 3.4.

###### proof of Theorem 3.4.

According to Lemma F.4, we directly obtain $\lim_{t\to\infty}\Delta_{t}=0$ if
$\lim_{t\to\infty}\left\|v_{t}^{2}\right\|_{2}=0$. In the following We prove
$\lim_{t\to\infty}\left\|v_{t}^{2}\right\|_{2}=0$ by contradiction. Assuming
that $\\{\left\|v_{t}^{2}\right\|_{2}\\}_{t}$ doesn’t converge to 0, i.e.,

$\displaystyle\exists\delta>0,\ \exists t_{1},t_{2},\cdots,\ s.t.\
\left\|v_{t_{i}}^{2}\right\|_{2}>\delta$ (34)

where $t_{i}$ tends to $+\infty$ as $i\to\infty$.

Let $\epsilon=\frac{1}{8}\delta(1-\lambda^{2})$, then we can find such $t_{j}$
that for any $t>t_{j}$,
$\left\|X_{t}\right\|_{2}^{2}-\left\|X_{t+1}\right\|_{2}^{2}\leq\epsilon$ by
Lemma F.2 , latter we will prove that under the assumption (34), there exists
$t>t_{j}$ such that
$\left\|X_{t}\right\|_{2}^{2}-\left\|X_{t+1}\right\|_{2}^{2}>\epsilon$ which
contradicts to Lemma F.2. Then we can also find a $t_{k}\geq t_{j}$ such that
for any $t>t_{k}$,

$\left\|\mathcal{B}_{t}\right\|_{2}\leq\min\\{\frac{\delta(1-\lambda^{2})}{8\left\|X_{0}\right\|_{2}},\frac{\delta(1-\lambda^{2})}{8\left\|X_{0}\right\|_{2}^{2}}\\}$

by $\lim_{t\to\infty}\mathcal{B}_{t}=0$, and for any $t_{s}\geq t_{k}$,
$\left\|v_{t_{s}}^{2}\right\|_{2}>\delta$. We choose such a $t_{s}$ and denote
it as $t$.

Now we give the bound for $\left\|\mathcal{B}_{t}X_{t}\right\|_{2}$,
$\left\|w_{t}^{1}\right\|_{2}$ and $\left\|w_{t}^{2}\right\|_{2}$,

$\displaystyle\left\|\mathcal{B}_{t}X_{t}\right\|_{2}$
$\displaystyle\leq\left\|\mathcal{B}_{t}\right\|_{2}\cdot\left\|X_{t}\right\|_{2}$
$\displaystyle\leq\min\\{\frac{\delta(1-\lambda^{2})}{8\left\|X_{0}\right\|_{2}},\frac{\delta(1-\lambda^{2})}{8\left\|X_{0}\right\|_{2}^{2}}\\}\cdot\left\|X_{0}\right\|_{2}$
$\displaystyle=\min\\{\frac{\delta(1-\lambda^{2})}{8},\frac{\delta(1-\lambda^{2})}{8\left\|X_{0}\right\|_{2}}\\}$
$\displaystyle\leq\frac{\delta(1-\lambda^{2})}{8},$

where the second inequality comes from Lemma F.2 . Together with
$\left\|w_{t}^{1}\right\|_{2}$ and $\left\|w_{t}^{2}\right\|_{2}$ are
perpendicular, which implies
$\left\|\mathcal{B}_{t}X_{t}\right\|_{2}^{2}=\left\|w_{t}^{1}\right\|_{2}^{2}+\left\|w_{t}^{2}\right\|_{2}^{2}$,
for $i=1,2$, we have

$\displaystyle\left\|w_{t}^{i}\right\|_{2}\leq\left\|\mathcal{B}_{t}X_{t}\right\|_{2}\leq\frac{\delta(1-\lambda^{2})}{8\left\|X_{0}\right\|_{2}}.$

Now we try to determine the relationship between $X_{t+1}$ and $X_{t}$,

$\displaystyle X_{t+1}$ $\displaystyle=(\mathcal{A}+\mathcal{B}_{t})X_{t}$
$\displaystyle=\mathcal{A}X_{t}+\mathcal{B}_{t}X_{t}$
$\displaystyle=\mathcal{A}(v_{t}^{1}+v_{t}^{2})+w_{t}^{1}+w_{t}^{2}$
$\displaystyle=(v_{t}^{1}+w_{t}^{1})+(\mathcal{A}v_{t}^{2}+w_{t}^{2}),$

where $v_{t}^{1}+w_{t}^{1}\in V_{1}$ and $\mathcal{A}v_{t}^{2}+w_{t}^{2}\in
V_{2}$, so $v_{t}^{1}+w_{t}^{1}$ and $\mathcal{A}v_{t}^{2}+w_{t}^{2}$ are
perpendicular, and

$\displaystyle\left\|X_{t+1}\right\|_{2}^{2}$
$\displaystyle=\left\|v_{t}^{1}+w_{t}^{1}\right\|_{2}^{2}+\left\|\mathcal{A}v_{t}^{2}+w_{t}^{2}\right\|_{2}^{2}$
$\displaystyle\leq\left\|v_{t}^{1}\right\|_{2}^{2}+\left\|w_{t}^{1}\right\|_{2}^{2}+2\left\|v_{t}^{1}\right\|_{2}\left\|w_{t}^{1}\right\|_{2}+\left\|\mathcal{A}v_{t}^{2}\right\|_{2}^{2}+\left\|w_{t}^{2}\right\|_{2}^{2}+2\left\|\mathcal{A}v_{t}^{2}\right\|_{2}\left\|w_{t}^{2}\right\|_{2}$
$\displaystyle\leq\left\|v_{t}^{1}\right\|_{2}^{2}+\lambda^{2}\left\|v_{t}^{2}\right\|_{2}^{2}+\left\|w_{t}^{1}\right\|_{2}^{2}+\left\|w_{t}^{2}\right\|_{2}^{2}+2\left\|v_{t}^{1}\right\|_{2}\left\|w_{t}^{1}\right\|_{2}+2\lambda\left\|v_{t}^{2}\right\|_{2}\left\|w_{t}^{2}\right\|_{2}$
$\displaystyle\leq\left\|v_{t}^{1}\right\|_{2}^{2}+\lambda^{2}\left\|v_{t}^{2}\right\|_{2}^{2}+\left\|\mathcal{B}_{t}X_{t}\right\|_{2}^{2}+2\left\|X_{0}\right\|_{2}\frac{\delta(1-\lambda^{2})}{8\left\|X_{0}\right\|_{2}}+2\lambda\left\|X_{0}\right\|_{2}\frac{\delta(1-\lambda^{2})}{8\left\|X_{0}\right\|_{2}}$
$\displaystyle\leq\left\|v_{t}^{1}\right\|_{2}^{2}+\lambda^{2}\left\|v_{t}^{2}\right\|_{2}^{2}+\frac{\delta(1-\lambda^{2})}{8}+2\frac{\delta(1-\lambda^{2})}{8}+2\lambda\frac{\delta(1-\lambda^{2})}{8}$
$\displaystyle\leq\left\|v_{t}^{1}\right\|_{2}^{2}+\lambda^{2}\left\|v_{t}^{2}\right\|_{2}^{2}+\frac{5}{8}\delta(1-\lambda^{2}).$

The second inequality comes from Lemma F.3, while the third inequality comes
from
$\left\|\mathcal{B}_{t}X_{t}\right\|_{2}^{2}=\left\|w_{t}^{1}\right\|_{2}^{2}+\left\|w_{t}^{2}\right\|_{2}^{2}$
and the upper bound for $\left\|w_{t}^{1}\right\|_{2}^{2}$ and
$\left\|w_{t}^{2}\right\|_{2}^{2}$. Then we conclude that

$\displaystyle\left\|X_{t}\right\|_{2}^{2}-\left\|X_{t+1}\right\|_{2}^{2}$
$\displaystyle\geq(\left\|v_{t}^{1}\right\|_{2}^{2}+\left\|v_{t}^{2}\right\|_{2}^{2})-(\left\|v_{t}^{1}\right\|_{2}^{2}+\lambda^{2}\left\|v_{t}^{2}\right\|_{2}^{2}+\frac{5}{8}\delta(1-\lambda^{2}))$
$\displaystyle\geq\delta(1-\lambda^{2})-\frac{5}{8}\delta(1-\lambda^{2})$
$\displaystyle=\frac{3}{8}\delta(1-\lambda^{2})>\frac{1}{8}\delta(1-\lambda^{2})=\epsilon,$

where a contradiction appears.

This completes the proof. ∎

##  Appendix G More Experiments

We provide additional experiments to demonstrate the behaviors of the
optimistic gradient and negative momentum methods in convergent perturbed
games that do not satisfy the BAP assumption. The numerical results reveal
cases where optimistic gradient/momentum method converge and cases where they
do not converge.

In the same setting as the experiments on Theorem 3.4, we find that both
optimistic gradient descent ascent and negative momentum method converge as
shown in Figure (8).

However, there are other cases in which these two algorithms do not converge.
In Figure (9), we present one such example. Here the payoff matrix is chosen
as $A=[[1,0],[0,0]],B=[[0,8],[0,0]]$ and

$\displaystyle A_{t}=\begin{cases}A,&t\textnormal{\ \ is \ odd}\\\
A+(1/t^{0.1})*B,&t\textnormal{\ \ is \ even}\end{cases}.$ (35)

In Figure (9), the numerical results show when using a step size of $0.015$,
optimistic gradient and negative momentum algorithms will diverge, but extra
gradient will converge. Based on these numerical results, we believe that
beyond the setting that satisfies the BAP assumption, there exists a more
complex dynamical behaviors of optimistic gradient and negative momentum
methods, which presents an interesting question for future exploration.

Figure 8:  Function curves of $\Delta_{t}$ for one game presented in
experiment of Theorem 3.4. in the paper. All these three algorithms converge.
Figure 9:  Function curves of $\Delta_{t}$. When using step size = 0.015,
extra-gradient converges, while both optimistic gradient descent ascent and
negative momentum method diverge.


problemx[1][]
Instance: Question:

11institutetext: The Institute of Mathematical Sciences, HBNI, Chennai, India
11email<EMAIL_ADDRESS>
# Sublinear-Space Approximation Algorithms for Max $r$-SAT

Arindam Biswas  Venkatesh Raman

###### Abstract

In the Max r-SAT problem, the input is a CNF formula with $n$ variables where
each clause is a disjunction of at most $r$ literals. The objective is to
compute an assignment which satisfies as many of the clauses as possible.
While there are a large number of polynomial-time approximation algorithms for
this problem, we take the viewpoint of space complexity following [Biswas et
al., Algorithmica 2021] and design sublinear-space approximation algorithms
for the problem.

We show that the classical algorithm of [Lieberherr and Specker, JACM 1981]
can be implemented to run in $n^{\operatorname{O}\left(1\right)}$ time while
using $\operatorname{O}\left(\log{n}\right)$ bits of space. The more advanced
algorithms use linear or semi-definite programming, and seem harder to carry
out in sublinear space. We show that a more recent algorithm with
approximation ratio $\sqrt{2}/2$ [Chou et al., FOCS 2020], designed for the
streaming model, can be implemented to run in time
$n^{\operatorname{O}\left(r\right)}$ using
$\operatorname{O}\left(r\log{n}\right)$ bits of space. While known streaming
algorithms for the problem approximate optimum values and use randomization,
our algorithms are deterministic and can output the approximately optimal
assignments in sublinear space.

For instances of Max r-SAT with planar incidence graphs, we devise a
factor-$(1-\epsilon)$ approximation scheme which computes assignments in time
$n^{\operatorname{O}\left(r/\epsilon\right)}$ and uses
$\max\left\\{\sqrt{n}\log{n},(r/\epsilon)\log^{2}{n}\right\\}$ bits of space.

###### Keywords:

Max SAT approximation sublinear space space-efficient memory-efficient planar
incidence graph

##  1 Introduction, Motivation and Our Results

Starting in the 70’s, there has been a long line of work on the approximation
properties of NP-hard problems. The classical approach has been to obtain
better-than-trivial approximations for such problems with polynomial-time
algorithms. Later on, a number of such problems were also studied in the
streaming model of computation, where an algorithm must read the input in a
fixed (possibly adversarial) sequence. The goal is typically to compute an
approximation by making a constant number of passes over the input using space
sublinear in the input size. Recently, there has been some interest in
studying approximation problems in the sublinear-space RAM model, a model
halfway between the RAM and streaming models of computation. In this paper, we
continue the work initiated in [5] and devise sublinear-space approximation
algorithms for Max r-SAT.

An instance of Max r-SAT is a CNF formula $F=C_{1}\wedge\dotsb\wedge C_{m}$,
where each of the clauses $C_{1},\dotsc,C_{m}$ is a disjunction of at most $r$
literals over a variable set $\left\\{x_{1},...,x_{n}\right\\}$. The objective
is to compute an assignment which satisfies as many of the clauses as
possible. Viewing the variables and clauses as an incidence structure yields
an incidence graph where clauses and variables are vertices, and there is an
edge between a variable $x$ and a clause $C$ whenever $x$ appears in $C$. We
call the restriction of Max r-SAT to instances with planar incidence graphs
Planar Max r-SAT.

The classical approximation algorithm [15] for Max r-SAT achieves an
approximation ratio of $1/2$ (shown to be $2/3$ in [7]). Later on, the ratio
was improved to $(\sqrt{5}-1)/2$ in [17]. Our first observation is that these
ratios can be achieved using logarithmic space. Algorithms computing
$(3/4)$-approximations are known [13], but they use linear or semi-definite
programming. Under logarithmic-space reductions, it is P-complete to
approximate Linear Programming to any constant factor [24]. In Section 3, we
show that the previously mentioned factor-$((\sqrt{5}-1)/2)$ and a more recent
factor-$(\sqrt{2}/2)$ approximation algorithm [8], devised for the streaming
model, can be implemented to use $\operatorname{O}\left(\log{n}\right)$ bits
of space. .

For Planar Max r-SAT, it is possible to compute factor-$(1-\epsilon)$
approximations in polynomial time for any constant $\epsilon>0$ [16]. In
Section 4, we give a sublinear-space implementation of this scheme using
recent results about computing tree decompositions [9] and BFS traversal
sequences [2].

#### The Model.

We use the standard RAM model and additionally constrain the amount of space
available to be sublinear in the input size. The input to an algorithm is
provided using some canonical representation, which it can read but not
modify, i.e. it has read-only access to the input. It also has read-write
access to a certain amount of auxiliary space. Output is written to a stream:
once something is output, the algorithm cannot read it back at a later point
as it executes. We count the amount of auxiliary space in single-bit units,
and the objective is to use as little auxiliary space as possible.

#### Related Work.

In the RAM model, earlier works with an emphasis on space efficiency include
reachability [23, 4, 21], sorting and selection [18, 11, 19] and graph
recognition [20, 1, 10]. In recent years, new results on the computability of
separators for planar graphs in sublinear space have been used to devise
sublinear-space algorithms for BFS [2] and DFS [14] with better running times
than algorithms for general graphs.

#### Results.

We study the question of what approximations may be achieved when the amount
of space available to an algorithm is sublinear in the input size. Our model
being more relaxed than the streaming model, we are able to compute
approximately optimal assignments for Max r-SAT instead of approximating
optimum values. On the other hand, our model is more restrictive than the RAM
model of classical approximation algorithms where the amount of space used by
an algorithm can potentially be polynomially large in the input size.

  * •

For general Max r-SAT (Section 3), we convert a classical algorithm of
Lieberherr and Specker [17] to our model, obtaining a
$((\sqrt{5}-1)/2)$-approximation algorithm which uses
$\operatorname{O}\left(\log{n}\right)$ bits of space. We also convert a more
recent algorithm of Chou et al. [8] to obtain a $(\sqrt{2}/2)$-approximation
algorithm which uses $\operatorname{O}\left(r\log{n}\right)$ bits of space.

  * •

For Planar Max r-SAT (Section 4), we show how a $(1-\epsilon)$-approximation
scheme of Khanna and Motwani [16] can be implemented to use
$\max\left\\{\sqrt{n},(r/\epsilon)\log{n}\right\\}$ bits of space.

##  2 Preliminaries

In this paper, we use the following standard notation and concepts. The set
$\left\\{0,1,\dotsc\right\\}$ of natural numbers is denoted by $\mathbb{N}$
and the set $\left\\{1,2,\dotsc\right\\}$ of positive integers is denoted by
$\mathbb{Z}^{+}$. For $n\in\mathbb{Z}^{+}$, $[n]$ denotes the set
$\left\\{1,2,\dotsc,n\right\\}$.

An $r$-CNF formula is a conjunction (OR) of disjunctions (AND) of at most $r$
literals (variables or their negations). The individual disjunctions are
called clauses of the formula. A clause that consists of a single literal is
called a unit clause. For $k\in[n]$, a $k$-clause is a clause which contains
exactly $k$ literals.

Let $F$ be a CNF formula with variables $x_{1},\dotsc,x_{n}$. An assignment
for $F$ is a function $\phi:[n]\to\left\\{0,1\right\\}^{n}$. The assignment is
said to satisfy a clause in $F$ if setting $x_{i}=\phi{1}\ (i\in[n])$ makes
some literal in the clause evaluate to $1$. If $\phi$ satisfies all clauses in
$F$, it is said to satisfy $F$.

###  2.1 Time and Space Overheads

In proofs, we measure resource costs in terms of overheads for individual
steps. Since the space available to an algorithm is limited, objects created
by processing the input are not stored, but recomputed on the fly. For
example, consider a procedure (call it A) that reads an input formula $F$ and
produces a subformula $F^{\prime}$ consisting of the unit clauses of $F$. The
procedure outputs $F^{\prime}$ as a stream $S_{F^{\prime}}$. Later on, when
another procedure (call it B) reads a portion of $S_{F^{\prime}}$, A
recomputes the entire stream $S_{F^{\prime}}$. Suppose the resource costs of A
are $t_{\texttt{A}}$ time and $s_{\texttt{A}}$ space, and assuming
$\operatorname{O}\left(1\right)$-time read costs, suppose the resource costs
of A are $t_{\texttt{B}}$ time and $s_{\texttt{B}}$ space.

In this scenario, we call $t_{\texttt{B}}$ and $s_{\texttt{B}}$ the resource
overhead of B. Combining this overhead with resource costs of A, we obtain the
actual resource costs of B: $t_{\texttt{B}}\cdot t_{\texttt{A}}$ time and
$s_{\texttt{B}}+s_{\texttt{A}}$ space.

###  2.2 Universal Hash Families

Algorithms appearing later on use the trick of randomized sampling to show
that certain good assignments exist and then derandomize the procedure by
using a $k$-_universal_ family of functions. A $k$-_universal hash_ family is
a family $\mathcal{H}$ of functions from $[n]$ to $[b]$, for positive integers
$n,k,b$ with $n\geq b,k$, such that for random variables $X_{i}$ ($i\in[n]$)
defined as $X_{i}=f(i)$ with $f$ sampled uniformly at random from
$\mathcal{H}$ (denoted $f\sim\mathcal{H}$), the probability—for any
$S\subseteq[n]$ with $\left\lvert S\right\rvert=k$ and any $a_{i}\in[l]\ (i\in
S)$—of the event $(\bigwedge_{i\in S}X_{i}=a_{i})$ is $1/b^{k}$. This
condition implies in particular that $X_{1},\dotsc,X_{n}$ are $k$-wise
independent and the probability of the event $(X_{i}=a_{i})$ is $1/b$.

Let $a\leq b$ be a positive integer, and consider the function
$\phi:[b]\to\left\\{0,1\right\\}$ defined by $\phi(x)=1$ if $x\leq a$ and
$\phi(x)=0$ otherwise. With $f\sim\mathcal{H}$ and $Y_{1},\dotsc,Y_{n}$
defined as $Y_{i}=\phi(f(i))$, it is easy to see that
$\operatorname{P}_{f\sim\mathcal{H}}\left(Y_{i}=1\right)=a/b$, and by the
$k$-universality of $\mathcal{H}$, the variables $Y_{1},\dotsc,Y_{n}$ are
$k$-wise independent. Note that $\left\\{\phi\circ f\mid
f\in\mathcal{H}\right\\}$ is in fact a $k$-universal hash family. With access
to $f\in\mathcal{H}$, the composition $\phi\circ f$ can be computed using
$\operatorname{O}\left(\log{n}\right)$ bits of extra space.

It is known that $k$-universal hash families such as $\mathcal{H}$ exist [12]
and can be computed in time $n^{\operatorname{O}\left(k\right)}$ using
$\operatorname{O}\left(k\log{n}\right)$ bits of space. The following
proposition is a combination of those results and the preceding discussion.

######  Proposition 1 (Fredman et al. [12])

Let $n,k,a,b\in\mathbb{Z}^{+}$ with $n\geq b\geq a$ and $n\geq k$. One can
enumerate a $k$-universal hash family $\operatorname{Univ}(n,k,a,b)$ for
$\left[[n]\to\left\\{0,1\right\\}\right]$ in time
$n^{\operatorname{O}\left(k\right)}$ using
$\operatorname{O}\left(k\log{n}\right)$ bits of space.

##  3 Max r-SAT

In this section, we devise sublinear-space $(\sqrt{5}-1)/2)$\- and
$(\sqrt{2}/2)$-approximation algorithms for Max r-SAT, with the former’s time
and space costs being independent of $r$. The following folklore result gives
a straightforward linear-time, logarithmic-space $(1/2)$-approximation.

######  Proposition 2 (Folklore)

For any $r$-CNF formula, either the all-$1$’s or the all-$0$’s assignment
satisfies at least half the clauses.

###  3.1 Factor-$((\sqrt{5}-1)/2)$ Approximation Algorithm

In what follows, we give a logarithmic-space implementation of the following
result.

######  Proposition 3 (Lieberherr and Specker [17], Theorem 1)

Let $F$ be an $r$-CNF formula with $m$ clauses. There is an assignment for $F$
which satisfies at least $(\sqrt{5}-1)m/2$ clauses.

######  Definition 1 ($2$-Satisfiability)

An $r$-CNF formula $F$ is called $2$-satisfiable if any two of its clauses can
be simultaneously satisfied, i.e. $F$ does not contain a pair $(l,\neg l)$ of
literals as clauses.

The following proposition is based on arguments in [17] (see also [25]).

###### Proposition 4

Let $F$ be a $2$-satisfiable $r$-CNF formula with $m$ clauses in which all
unit clauses are positive literals. For the pairwise-independent random
assignment where each variable of $F$ is set to $1$ with probability
$p=0.618\approx(\sqrt{5}-1)/2$, the expected number of satisfied clauses is
$0.618m$.

We now show how the above proposition can be used to compute
$0.618$-approximate optimal Max r-SAT assignments for general $r$-CNF formulas
in logarithmic space.

###### Theorem 3.1

For any instance of Max r-SAT with $n$ variables, one can compute a
$0.618$-approximate optimal assignment in time
$n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of space.

###### Proof

Let $F$ be an $r$-CNF formula with variables $x_{1},\dotsc,x_{n}$. In what
follows, we describe an algorithm which proves the claim.

Computing an equivalent $2$-satisfiable formula $F^{\prime}$. For each clause
$C$ in $F$ with at least two literals, check if any variables $x$ appearing in
$C$ also appear as a negated clauses $\neg x$ in $F$. If they do, flip the
$x$-literals (replace $x$ with $\neg x$ or $\neg x$ with $x$) in $C$ and
output the resulting clause. Otherwise, output $C$. The clauses not output yet
are unit clauses, i.e. they have exactly $1$ literal. For each variable
$x_{i}$, check if $x_{i}$ appears as a unit clause in $F$. If it does, output
$x_{i}$. Then output the special flag #NEG, to indicate that clauses to follow
appear negated in $F$. For each variable $x_{i}$, check if it appears as a
unit clause $\neg x_{i}$ in $F$. If it does, check if the unit clause $x_{i}$
also appears in $F$. If both $\neg x_{i}$ and $x_{i}$ are clauses in $F$,
output nothing. Otherwise, output $x_{i}$. Observe that the only clauses of
$F$ not output are unit clauses that appear in pairs $(l,\neg l)$.

Let $F^{\prime}$ be the conjunction of the clauses output and $S_{F^{\prime}}$
be the stream output. With random access to $F$, $S_{F}$ is produced in time
$n^{\operatorname{O}\left(1\right)}$ using
$\operatorname{O}\left(\log{n}\right)$ bits of space. Clearly, $F^{\prime}$ is
$2$-satisfiable. Let $\phi$ be an assignment for $F^{\prime}$. Define
$\phi^{\prime}(x_{i})=1-\phi(x_{i})$ for every $x_{i}$ appearing after the
#NEG flag in $S_{F^{\prime}}$ and define $\phi^{\prime}(x_{i})=\phi(x_{i})$
otherwise. It is easy to see that $\phi$ satisfies the same number of clauses
in $F^{\prime}$ as $\phi^{\prime}$ does in $F$, and that given access to
$S_{F^{\prime}}$ and $\phi$, the overhead for computing $\phi^{\prime}$ is
$n^{\operatorname{O}\left(1\right)}$ time and
$\operatorname{O}\left(\log{n}\right)$ space. We use this transformation later
on to compute an assignment for $F$ from an assignment for $F^{\prime}$.

Computing an assignment for $F^{\prime}$. Using the procedure of Proposition
1, compute a $2$-universal hash family
$\mathcal{H}=\operatorname{Univ}(n,2,618,1000)$ and denote the stream of
functions by $S_{H}$. Note that with $X_{i}\sim\mathcal{H}_{i}$ for $i\in[n]$,
the random variables $X_{1},\dotsc,X_{n}$ form a pairwise-independent random
assignment. Thus, one of the assignments in $S_{H}$ achieves (for the
$2$-satisfiable formula $F^{\prime}$) the expectation value in Proposition 4.

Let $m^{\prime}$ be the number of clauses in $F^{\prime}$. For each assignment
$\phi$ in $S_{H}$, scan $S_{F}^{\prime}$ to determine the number $c$ of
clauses $\phi$ satisfies. If $c>0.618m^{\prime}$, output $\phi$ and skip to
the next step. By Proposition 1, $\operatorname{Hash}(n,2,618,1000)$ is
computed in time $n^{\operatorname{O}\left(1\right)}$ and
$\operatorname{O}\left(\log{n}\right)$ bits of space, since $k=2$ is constant.
The overhead of this step is therefore $n^{\operatorname{O}\left(1\right)}$
time and $\operatorname{O}\left(\log{n}\right)$ bits of space. Denote the
output stream of this step by $S_{\phi}$.

Computing an assignment for $F$. Now convert the assignment $\phi$ from the
previous step to an assignment $\phi^{\prime}$ (according to the
transformation described earlier) as follows. For each $x_{i}$, scan
$S_{\phi}$ to determine the value $v=\phi(x_{i})$, and scan $S_{F^{\prime}}$
to determine if $x_{i}$ appears after the #NEG (it was flipped). If it does,
output the assignment $\phi^{\prime}(x_{i})=1-v$. Otherwise, output the
assignment $\phi^{\prime}(x_{i})=v$. Since $\phi$ satisfies $c\geq
0.618m^{\prime}$ clauses in $F^{\prime}$, $\phi^{\prime}$ satisfies the same
number of clauses in $F$. In particular, it satisfies at least a
$0.618$-fraction of the non-unit clauses, and unit clauses that do not appear
in $(l,\neg l)$ pairs.

Of the pairs $(l,\neg l)$ of unit clauses appearing in $F$, exactly half are
satisfied by any assignment for the variables appearing in them. Now for each
$x_{i}$, scan $S_{\phi}$, to determine if $\phi$ assigns it a value. If it
does not, output the assignment $\phi^{\prime}(x_{i})=1$. Clearly,
$\phi^{\prime}$ now also satisfies exactly half of the unit clauses in $F$
appearing in pairs $(l,\neg l)$, i.e. it is an optimal assignment for those
clauses. Thus, $\phi^{\prime}$ is $0.618$-optimal assignment for all of $F$.
The overhead of this conversion step is also
$n^{\operatorname{O}\left(1\right)}$ time and
$\operatorname{O}\left(\log{n}\right)$ bits of space.

Since the overheads for all steps are $n^{\operatorname{O}\left(1\right)}$
time and $\operatorname{O}\left(\log{n}\right)$ space, the overall running
time is
${(n^{\operatorname{O}\left(1\right)})}^{3}=n^{\operatorname{O}\left(1\right)}$
and the space used is
$3\cdot\operatorname{O}\left(\log{n}\right)=\operatorname{O}\left(\log{n}\right)$.
∎

###  3.2 Factor-$(\sqrt{2}/2)$ Approximation Algorithm

In the following, we adapt arguments in [8] to devise a
$(\sqrt{2}/2)$-approximation algorithm which runs in time
$n^{\operatorname{O}\left(r\right)}$ and uses
$\operatorname{O}\left(r\log{n}\right)$ bits of space. Consider the following
definitions.

######  Definition 2 (Bias)

Let $F$ be an $r$-CNF formula with variables $x_{1},\dotsc,x_{n}$. For
$i\in[n]$, the bias of $x_{i}$ is
$\operatorname{bias}(x_{i})=\sum_{j\in[r]}(\\#(j\text{-clauses containing}\
x_{i})-\\#(j\text{-clauses containing}\ \neg x_{i}))/2^{j}$.

The bias of the entire formula is
$\operatorname{bias}(F)=\sum_{i\in[n]}\left\lvert\operatorname{bias}(x_{i})\right\rvert$
and the formula $F$ is called positively biased if
$\operatorname{bias}(x_{i})\geq 0$ for each $i\in[n]$.

The next proposition shows that depending on whether the bias of a formula is
smaller than a certain value, one can satisfy a good proportion (in
expectation) of the clauses in it by setting each variable to $1$ with fixed
(bias-dependent) probability.

######  Proposition 5 (Chou et al. [8])

Let $F$ be a positively-biased $r$-CNF formula with $m$ clauses. For
$i\in[r]$, let $m_{i}$ be the number of $i$-clauses in $F$. The following
statements are true.

  * •

The all-$1$’s assignment satisfies at least
$\frac{\operatorname{bias}(F)}{2}+\sum_{i\in[r]}\frac{im_{i}}{2^{i}}$ clauses
in $F$.

  * •

When $\operatorname{bias}(F)\leq
b^{*}=4\sum_{i\in[r]}\left(1-\frac{i+1}{2^{i}}\right)m_{i}$, an $r$-wise
independent random assignment where variables are set to $1$ with probability
$\frac{m-\operatorname{bias}(F)}{2m-4\operatorname{bias}(F)}\leq 1$ satisfies,
in expectation, at least
$\sum_{i\in[r]}\left(1-\frac{1}{2^{i}}\right)m_{i}+\frac{\operatorname{bias}(F)^{2}}{4b^{*}}$
clauses in $F$.

  * •

The best of the two assignments above satisfies at least a
$(\sqrt{2}/2)$-fraction of the maximum number of simultaneously-satisfiable
clauses in $F$.

We now show how the above proposition can be used to compute good
approximations in sublinear space. For any $r$-CNF formula $F$, we first
compute an equivalent positively-biased formula $F^{\prime}$ and then using
Proposition 1, compute an assignment for $F^{\prime}$ which is a
$(\sqrt{2}/2)$-approximation. We then convert this to an assignment for $F$
satisfying the same number of clauses.

###### Theorem 3.2

For any instance of Max r-SAT with $n$ variables, one can compute a
$(\sqrt{2}/2)$-approximate optimal assignment in time
$n^{\operatorname{O}\left(r\right)}$ using
$\operatorname{O}\left(r\log{n}\right)$ bits of space.

###### Proof

Let $F$ be an $r$-CNF formula with variables $x_{1},\dotsc,x_{n}$ and for
$i\in[n]$, let $m_{i}$ be the number of $i$-clauses in $F$. In what follows,
we describe an algorithm which proves the claim.

Computing $\operatorname{bias}(F)$ and $b^{*}$. Set $b_{F},b^{*}\leftarrow 0$.
For each $i\in[n]$, compute $b_{i}=\operatorname{bias}(x_{i})$ and $m_{i}$. It
is easy to see that with random access to $F$, this can be done in logarithmic
space. Set $b_{F}\leftarrow b_{F}+\left\lvert b_{i}\right\rvert,\
b^{*}\leftarrow b^{*}+(1-(i+1)/2^{i})m_{i}$, and if $b_{i}<0$, output $x_{i}$
to indicate that $x_{i}$ has negative bias in $F$. Then discard
$(b_{i},m_{i})$ and move to the next iteration. Finally, store $b_{F}$ and
$b^{*}\leftarrow 4b^{*}$ for later steps using
$\operatorname{O}\left(\log{n}\right)$ bits of space. The entire loop takes
time $n^{\operatorname{O}\left(1\right)}$ and uses
$\operatorname{O}\left(\log{n}\right)$ bits of space. Let $S_{B}$ be the
stream output.

Computing an equivalent positively-biased formula $F^{\prime}$. For each
clause $C$ in $F$, check if any variables $x$ appearing in $C$ also appear in
the stream $S_{B}$. If they do, flip the $x$-literals (replace $x$ with $\neg
x$ or $\neg x$ with $x$) in $C$ and output the resulting clause. Otherwise,
output $C$. Observe that the variables $x$ flipped are precisely those for
which $\operatorname{bias}(x)<0$ in the previous step. Thus, the clauses
output form a positively-biased formula. Denote the output stream by
$S_{F^{\prime}}$. The overhead of this step is
$n^{\operatorname{O}\left(1\right)}$ time and
$\operatorname{O}\left(\log{n}\right)$ space.

Computing an assignment for $F^{\prime}$. If $b_{F}>b^{*}$, then output the
all-$1$’s assignment and skip to the next step. Otherwise, using the procedure
of Proposition 1, compute an $r$-universal hash family
$\mathcal{H}=\operatorname{Univ}(n,r,\left\lceil
m-b_{F}\right\rceil,\left\lceil 2m-4b_{F}\right\rceil)$ and denote the stream
of functions by $S_{H}$. Similarly as in the proof of Theorem 3.1, one of the
assignments in $S_{H}$ achieves the expectation value in Proposition 5.

For each assignment $\phi$ in $S_{H}$, scan $S_{F}^{\prime}$ to determine the
number $c$ of clauses $\phi$ satisfies. If
$c\geq{b_{F}}^{2}/(16\sum_{i=2}^{k}(1-(i+1)/2^{i})m_{i})$, output $\phi$ and
skip to the next step. The family of assignments is computed in time
$n^{\operatorname{O}\left(r\right)}$ and
$\operatorname{O}\left(r\log{n}\right)$ bits of space, so the overhead of this
step is $n^{\operatorname{O}\left(r\right)}$ time and
$\operatorname{O}\left(r\log{n}\right)$ bits of space. Denote the output
stream of this step by $S_{\phi}$.

Computing an assignment for $F$. Convert the assignment $\phi$ from the
previous step to an assignment $\phi^{\prime}$ for $F$ as follows. For each
$x_{i}$, scan $S_{\phi}$ to determine the value $v=\phi(x_{i})$, and scan
$S_{B}$ to check if $x_{i}$ appears in it (it was flipped). If it does, output
the assignment $\phi^{\prime}(x_{i})=1-v$. Otherwise, output the assignment
$\phi^{\prime}(x_{i})=v$. Clearly, $\phi$ satisfies the same number of clauses
in $F^{\prime}$ as $\phi^{\prime}$ does in $F$. By Proposition 5, this number
is at least a $(\sqrt{2}/2)$-fraction of the maximum number of simultaneously-
satisfiable clauses in $F$. With access to $S_{\phi}$ and $S_{B}$, the
overhead of this step is $n^{\operatorname{O}\left(1\right)}$ time and
$\operatorname{O}\left(\log{n}\right)$ space.

Thus, the algorithm outputs a $(\sqrt{2}/2)$-approximate optimal assignment as
required. Observe that the maximum overhead of any of the steps is
$n^{\operatorname{O}\left(r\right)}$ time and
$\operatorname{O}\left(r\log{n}\right)$ space. Combining the (constantly many)
overheads, the overall running time is
$n^{\operatorname{O}\left(r\right)\cdot\operatorname{O}\left(1\right)}=n^{\operatorname{O}\left(r\right)}$
and the space used is
$\operatorname{O}\left(r\log{n}\right)\cdot\operatorname{O}\left(1\right)=\operatorname{O}\left(r\log{n}\right)$.
∎

##  4 Planar Max r-SAT

In this section, we devise a sublinear-space PTAS for Planar Max r-SAT along
the lines of [16] using the partitioning approach in [3] for planar graph
problems. We use the following result to perform a BFS traversal of (the
incidence graphs of) the input instances in sublinear space.

######  Proposition 6 (Chakraborty and Tewari [6], Theorem 1)

There is an algorithm which takes as input a planar graph on $n$ vertices and
computes a BFS sequence for $G$ in time $n^{\operatorname{O}\left(1\right)}$
using $\operatorname{O}\left(\sqrt{n}\log{n}\right)$ bits of space.

The next result shows how to use the BFS traversal procedure to partition—in
sublinear space—the input formulas into subformulas of bounded diameter.

###### Lemma 1

Let $F$ be an $r$-CNF formula with $n$ variables and $m$ clauses that has a
planar incidence graph and let $k\in\mathbb{N}$. One can compute a sequence
$F_{1},\dotsc,F_{l}$ of subformulas of $F$ such that

  1. 1.

the diameter of the incidence graph of each $F_{i}$ ($i\in[l]$) is at most
$k$,

  2. 2.

$F_{i}$ and $F_{j}$ have no variables in common for all $i,j\in[l]$ with
$i\neq j$, and

  3. 3.

$F_{1},\dotsc,F_{l}$ together contain at least $(1-1/k)m$ clauses of $F$.

The procedure runs in time $n^{\operatorname{O}\left(1\right)}$ and uses
$\operatorname{O}\left(\sqrt{n}\log{n}\right)$ bits of space.

###### Proof

Let ${x_{1},\dotsc,x_{n}}$ be the set of variables in $F$,
$\left\\{C_{1},\dotsc,C_{m}\right\\}$ be the set of clauses in $F$, $G_{F}$ be
the incidence graph of $F$, and $V_{F}$ (resp. $C_{F}$) be the vertices of
$G_{F}$ corresponding to the variables (resp. clauses) of $F$. In what
follows, we describe a procedure which proves the claim.

Adding a dummy vertex. This step ensures that $G_{F}$ is connected. Determine
the connected components of $G_{F}$ using the connectivity algorithm of Asano
et al. [2]: for any two vertices, it runs in time
$n^{\operatorname{O}\left(1\right)}$ and uses
$\operatorname{O}\left(\sqrt{n}\log{n}\right)$ bits of space to check if the
two vertices are connected. Then add a dummy variable vertex $x_{n+1}$ which
has an edge to an arbitrary clause vertex in each connected component, making
$G_{F}$ connected. Additionally, add the clause $\neg x_{n+1}$ (with an edge
to $x_{n+1}$) to ensure that assignments for the formula $F^{\prime}$
determined by the resulting graph $G_{F^{\prime}}$ are in $1$-$1$
correspondence with assignments for $F$. Now output $F^{\prime}$ and
$G_{F^{\prime}}$, and denote this output stream by $S_{F^{\prime}}$. With
random access to $G_{F}$, it is not hard to see that this transformation runs
in time $n^{\operatorname{O}\left(1\right)}$ and uses
$\operatorname{O}\left(\sqrt{n}\log{n}\right)$ bits of space.

Determining the BFS levels of $G_{F^{\prime}}$. Consider a BFS traversal of
$G_{F^{\prime}}$ starting at (the variable vertex corresponding to) $x_{n+1}$.
Suppose the depth of the traversal is $d_{0}$. Let $d=d_{0}$ if $d_{0}$ is
even and $d=d_{0}+1$ otherwise. For $i\in[d]$, set $L_{i}=\left\\{v\in
V(G_{F^{\prime}})\mid\operatorname{dist}(u,v)=i-1\right\\}$. Observe that
$L_{1},\dotsc,L_{d}$ are precisely the levels of the BFS tree, with
$L_{i}\subseteq V_{F}$ for odd $i$ and $L_{i}\subseteq C_{F}$ for even $i$.

Splitting $G_{F}$. Consider the following subsets of
$\operatorname{V}\left(G_{F^{\prime}}\right)$.

  * •

For $i\in[d/2-1]$, let $U_{i}=L_{2i}\cup L_{2i+1}\cup L_{2i+2}$. Observe that
$U_{i}\cap U_{j}\neq\emptyset$ iff $\left\lvert i-j\right\rvert\leq 1$ and for
$i\in[d/2-1]$, $U_{i}\cap U_{i+1}=L_{2i+2}$.

  * •

For $i\in\left\\{0,\dotsc,k-1\right\\}$, let $W_{i}=\bigcup_{j\equiv
i\pmod{k}}U_{j}$. Observe that $W_{i}\cap W_{j}\neq\emptyset$ iff
$i-j\equiv\pm 1\pmod{k}$ and for $i\in[d/2-1]$, $W_{i}\cap
W_{i+1}=\bigcup_{j\equiv i\pmod{k}}L_{2j+2}$.

  * •

For any $A\subseteq V_{F}\cup C_{F}$, let $C(A)$ be the clause vertices that
appear in $A$, i.e. $C(A)=A\cap C_{F}$.

Clearly, for $i\in[d/2-1]$, $C(W_{i})=\bigcup_{j\equiv i\pmod{k}}L_{2j}\cup
L_{2j+2}$ and $C_{F}=\bigcup_{i\in{0,\dotsc,k-1}}C(W_{i})$. By the inclusion-
exclusion principle, we have

$\displaystyle\left\lvert C(W_{0})\right\rvert+\dotsb$
$\displaystyle+\left\lvert C(W_{k-1})\right\rvert=\left\lvert
C_{F}\right\rvert+\left\lvert C(W_{0})\cap
C(W_{1})\right\rvert+\dotsb+\left\lvert C(W_{k-1})\cap C(W_{0})\right\rvert$
$\displaystyle=\left\lvert C_{F}\right\rvert+\sum_{i\in\left\\{0,\dotsc
k-1\right\\}}\left\lvert L_{2j+1}\right\rvert\leq\left\lvert
C_{F}\right\rvert+\left\lvert C_{F}\right\rvert=2\left\lvert
C_{F}\right\rvert.$

Thus, for some $i\in\left\\{0,\dotsc,k-1\right\\}$, we have $\left\lvert
C(W_{i})\right\rvert\leq 2\left\lvert C_{F}\right\rvert/k$, i.e. $W_{i}$
contains at most a $(2/k)$-fraction of the clauses in $F^{\prime}$ (and $F$).
Consider the graph $G_{F^{\prime}}-W_{i}$. Observe that $W_{i}$ comprises
groups of $3$ consecutive layers of the BFS traversal, and consecutive groups
are $k-2$ layers apart. Thus, removing $W_{i}$ from $G_{F^{\prime}}$
disconnects $G_{F^{\prime}}$ into connected components which contain at most
$k-2$ layers of the BFS traversal each, i.e. their diameters are at most
$k-2$. It follows that the formula $F^{+}$ corresponding to
$G_{F^{\prime}}-W_{i}$ satisfies the conditions of the claim.

To compute $F^{+}$, perform the following steps. Using the procedure of
Proposition 6, perform a BFS traversal of the $G_{F^{\prime}}$ portion of
$S_{F}^{\prime}$, starting at $x_{n+1}$. Let $S_{B}$ be the stream produced by
this procedure. The overhead of the procedure is
$n^{\operatorname{O}\left(1\right)}$ time and
$\operatorname{O}\left(\sqrt{n}\log{n}\right)$ bits of space. For each
$i\in[k]$, scan $S_{B}$ to determine the number $\left\lvert
C(W_{i})\right\rvert$ of clauses in $W_{i}$. For $i$ achieving the smallest
$\left\lvert C(W_{i})\right\rvert$ in the loop, scan $S_{B}$ and output only
the levels (and edges between them) which do not appear in $W_{i}$. Let
$S_{F^{+}}$ be this output stream. Now scan $S_{F+}$, and for each sequence of
consecutive (connected) levels, output the subformula of $F$ induced by those
levels. Observe that $S_{F^{+}}$ is produced by scanning $S_{F^{\prime}}$ and
the final output is produced by scanning $S_{F^{+}}$. Each scan only involves
counting elements in the stream and truncating parts of the stream to produce
the output stream. Thus, the overhead of this entire step is
$n^{\operatorname{O}\left(1\right)}$ time and
$\operatorname{O}\left(\sqrt{n}\log{n}\right)$ space.

For the various steps, the maximum overhead is
$n^{\operatorname{O}\left(1\right)}$ time and
$\operatorname{O}\left(\sqrt{n}\log{n}\right)$ bits of space. Thus, combining
the overheads for the various steps, the resource costs of the entire
algorithm are $n^{\operatorname{O}\left(1\right)}$ time and $\sqrt{n}\log{n}$
bits of space. ∎

The next two results allow use to compute tree decompositions for incidence
graphs of bounded diameter in sublinear space.

######  Proposition 7 (Robertson and Seymour [22], Theorem 2.7)

The treewidth of any planar graph with diameter $d$ is at most $3d+1$.

######  Proposition 8 (Elberfeld et al.[9], Lemma III.1)

Let $G$ be a graph on $n$ vertices with treewidth $k\in\mathbb{N}$. One can
compute a tree decomposition of width $4k+1$ for $G$ such that the
decomposition tree is rooted, binary and has depth
$\operatorname{O}\left(\log{n}\right)$. The procedure runs in time
$n^{\operatorname{O}\left(k\right)}$ and uses
$\operatorname{O}\left(k\log{n}\right)$ bits of space.

[h]  Input: $(T,v,\mathcal{B},\mathcal{P}\psi)$ $max\leftarrow
0,\phi_{max}\leftarrow\emptyset$;

2 if  _$v$ has no children in $T$_ then

3 store $V_{v}$, the set of variables in $B_{v}$ that extend $\psi$ let
$\mathcal{A}_{v}$ be the set of assignments for variables ;

4 foreach  _$\phi\in\mathcal{A}_{v}$_ do

5 determine $val$, the number of clauses appearing in $B_{v}$ that $\phi$
satisfies;

6 if  _$val >max$_ then

7 $max\leftarrow val,\ \phi_{max}\leftarrow\phi$

8

9 return _$(max,\phi_{max})$_

10else

11 determine the left child $v_{l}$ and the right child $v_{r}$ of $v$ in $T$
if they exist;

12 store $V_{v}$, the set of variables in $B_{v}$, and those in $B_{v_{l}}$
and $B_{v_{r}}$ adjacent to clause variables in $B_{v}$;

13 let $\mathcal{A}_{v}$ be the set of assignments for $V_{v}$ that extend
$\psi$;

14 foreach  _$\phi\in\mathcal{A}_{v}$_ do

15
$(val_{l},\phi_{l})\leftarrow\texttt{BdTWMaxSAT}(T,v_{l},\mathcal{B},\phi)$;

16
$(val_{r},\phi_{r})\leftarrow\texttt{BdTWMaxSAT}(T,v_{r},\mathcal{B},\phi)$;

17 if  _$val_{l}+val_{r} >max$_ then

18 $max\leftarrow val_{l}+val_{r},\ \phi_{max}\leftarrow\phi_{l}\cup\phi_{r}$

19

20 return _$(max,\phi_{max})$_

BdTWMaxSAT(): find an optimal assignment

We now show how one can solve Planar Max r-SAT exactly on formulas with
incidence graphs of bounded diameter.

###### Lemma 2

Let $F$ be an $r$-CNF formula with $n$ variables that has a planar incidence
graph with diameter $k\in\mathbb{N}$. One can compute an assignment for $F$
satisfying the maximum number of clauses in time
$n^{\operatorname{O}\left(rk\right)}$ using
$\operatorname{O}\left(rk\log^{2}{n}\right)$ bits of space.

###### Proof

Let $G$ be the incidence graph of $F$. Since the diameter of $G$ is $k$, its
treewidth is at most $3k+1$ (Proposition 7). Consider a tree decomposition
$(T,\mathcal{B})$ for $G$ computed by the procedure of Proposition 8. $T$ is
the underlying tree (rooted at a vertex
$v_{r}\in\operatorname{V}\left(T\right)$) and $\mathcal{B}=\left\\{B_{v}\mid
v\in\operatorname{V}\left(T\right)\right\\}$ is the set of bags in the
decomposition. By the proposition, the depth of $T$ is
$\operatorname{O}\left(\log{n}\right)$ and its width is at most
$4\cdot(3k+1)+1=\operatorname{O}\left(k\right)$, i.e. $\left\lvert
B_{v}\right\rvert=\operatorname{O}\left(k\right)$ for all
$v\in\operatorname{V}\left(T\right)$.

For each $v\in\operatorname{V}\left(T\right)$, let $F_{v}$ be the subformula
of $F$ consisting of all clauses appearing in bags of the subtree of $T$
rooted at $v$. Let $V_{v}$ be the set of variables in $B_{v}$, and those in
the bags of $v$’s children (if they exist) that are adjacent to variables in
$B_{v}$.

In what follows, we prove that BdTWMaxSAT$(T,v_{r},\mathcal{B},\emptyset)$
($\emptyset$ denotes the empty assignment) computes an assignment for $F$
satisfying the maximum number of clauses. We momentarily assume constant-time
access to $G$ and $(T,\mathcal{B})$.

Assume for induction that for any $v\in V{T}$, any assignment $\phi$ for
$V_{v}$ and any child $v_{c}$ of $v$, that
$\texttt{BdTWMaxSAT}(T,v_{c},\mathcal{B},\phi)$ returns an assignment for
$F_{v_{c}}$ which extends $\phi$ and satisfies the maximum number of clauses
in $F_{v_{c}}$ among all such assignments. Now consider a procedure call
$\texttt{BdTWMaxSAT}(T,v,\mathcal{B},\psi)$. The procedure first determines if
$v$ has any children. If it does not, then it iterates over all assignments
for variables in $B_{v}$ that extend $\phi$, finds one that satisfies the
maximum number of clauses in $F_{v}$ and returns it. Thus, the procedure is
correct in the base case. Since $\left\lvert V_{v}\right\rvert\leq\left\lvert
B_{v}\right\rvert=\operatorname{O}\left(k\right)$, the number of such
assignments is $2^{\operatorname{O}\left(k\right)}$. The call stack stores
$\psi$ and $V_{v}$, so the assignments can be enumerated in time
$2^{\operatorname{O}\left(k\right)}\cdot n^{\operatorname{O}\left(1\right)}$
using $\operatorname{O}\left(rk\log{n}\right)$ bits of extra space. Thus, this
section of the procedure runs in time $2^{\operatorname{O}\left(k\right)}\cdot
n^{\operatorname{O}\left(1\right)}$ and uses
$\operatorname{O}\left(k\log{n}\right)$ bits of space.

In the other case, i.e. $v$ has children, the procedure determines the left
and right children of $v$ by scanning $(T,\mathcal{B})$. It then stores
$V_{v}$, which is polynomial-time and uses
$\operatorname{O}\left(rk\log{n}\right)$ bits of space, since each clause in
$B_{v}$ has at most $r$ literals and thus $\left\lvert V_{v}\right\rvert\leq
r\cdot\left\lvert B_{v}\right\rvert=\operatorname{O}\left(rk\log{n}\right)$.
The loop iterates over the set $\mathcal{A}_{v}$ of assignments for $V_{v}$
that extend $\psi$. The assignments can be enumerated (since $\psi$ and
$V_{v}$ are stored on the call stack) in time
$2^{\operatorname{O}\left(rk\right)}\cdot n^{\operatorname{O}\left(1\right)}$
using $\operatorname{O}\left(rk\log{n}\right)$ bits of extra space. Next, the
procedure calls itself recursively and stores the tuples returned. Because of
the inductive assumption, $\phi_{l}$ (resp. $\phi_{r}$) extends $\phi$ and
satisfies the maximum number of clauses in $F_{v_{l}}$ (resp. $F_{v_{r}}$)
among all such assignments.

Observe that because $(T,\mathcal{B})$ is a tree decomposition, the variables
outside of $V_{v}$ that $\phi_{l}$ sets are distinct from the variables
outside of $V_{v}$ that $\phi_{r}$ sets. Thus, $\phi_{l}$ and $\phi_{r}$ do
not conflict with each other. In the loop, the procedure finds an extension
$\phi$ of $\psi$ such that its extensions $\phi^{max}_{l}$ and
$\phi^{max}_{r}$, respectively, satisfy the maximum number of clauses in
$F_{l}$ and $F_{r}$. Overall, $\phi$ is an extension of $\psi$ which satisfies
the maximum possible number of clauses in $F_{v}$. This proves the inductive
claim, and thus the procedure is correct.

We now prove the resource bounds of the procedure (assuming constant-time
access to $G$ and $(T,\mathcal{B})$). Observe that in each recursive call, the
the individual steps $\operatorname{O}\left(rk\log{n}\right)$ bits of space
and the loops also use $\operatorname{O}\left(rk\log{n}\right)$ bits of space.
Since $T$ has depth $\operatorname{O}\left(\log{n}\right)$, the depth of the
recursion tree is also $\operatorname{O}\left(\log{n}\right)$, and therefore
the call $\texttt{BdTWMaxSAT}(T,r,\mathcal{B},\emptyset)$ uses a total of
$\operatorname{O}\left(rk\log^{2}{n}\right)$ bits of space.

Outside of the recursive calls, the individual steps of the procedure are
polynomial-time and the total running time for the other operations in the
loops is $2^{\operatorname{O}\left(rk\right)}\cdot
n^{\operatorname{O}\left(1\right)}$. Thus, if the recursive calls take time
$T$, the overall running time of the procedure is
$2^{\operatorname{O}\left(rk\right)}\cdot
2T+2^{\operatorname{O}\left(rk\right)}\cdot
n^{\operatorname{O}\left(1\right)}$. Since the depth of the recursion tree is
$\operatorname{O}\left(\log{n}\right)$, this expression solves to
$n^{\operatorname{O}\left(rk\right)}$.

Now consider the overheads for computing $G$ and $(T,\mathcal{B})$. $G$ is
clearly computable in polynomial time and logarithmic space and by Proposition
8, $(T,\mathcal{B})$ is computable in time
$n^{\operatorname{O}\left(k\right)}$ using
$\operatorname{O}\left(k\log{n}\right)$ bits of space. The real resource costs
of $\texttt{BdTWMaxSAT}(T,v_{r},\mathcal{B},\emptyset)$ are therefore
$n^{\operatorname{O}\left(rk\right)}\cdot
n^{\operatorname{O}\left(k\right)}=n^{\operatorname{O}\left(rk\right)}$ time
and
$\operatorname{O}\left(rk\log^{2}{n}\right)+\operatorname{O}\left(k\log{n}\right)=\operatorname{O}\left(rk\log^{2}{n}\right)$
bits of space. ∎

The next theorem combines the previous results to devise a sublinear-space
PTAS for Planar Max r-SAT.

###### Theorem 4.1

For any $0<\epsilon<1$, one can compute $(1-\epsilon)$-approximate optimal
assignments for Planar Max r-SAT in time
$n^{\operatorname{O}\left(r/\epsilon\right)}$ using
$\max\left\\{\sqrt{n}\log{n},(r/\epsilon)\log^{2}{n}\right\\}$ bits of space.

###### Proof

Consider the following algorithm. Using the procedure of Lemma 1 with
$k=\left\lceil 1/\epsilon\right\rceil$, partition $F$ into subformulas
$F_{1},\dotsc,F_{l}$. Then for each $i\in[l]$, use the procedure of Lemma 2,
compute an exact solution for $F_{i}$ and output an assignment. In the end,
output assignments $x=0$ for all variables $x$ not appearing in
$F_{1},\dotsc,F_{l}$.

Observe that since the partitioning procedure outputs the subformulas as a
stream $S_{F}=F_{1},\dotsc,F_{l}$, each access to $F_{i}$ costs a single pass
over $S_{F}$, which adds only an $n^{\operatorname{O}\left(1\right)}$-time,
$\operatorname{O}\left(\log{n}\right)$-space overhead. By Lemma 1, the
partitioning procedure runs in time $n^{\operatorname{O}\left(1\right)}$ and
uses $\operatorname{O}\left(\sqrt{n}\log{n}\right)$ bits of space. Combining
the overhead for access to $F_{i}$ and the resource bounds from Lemma 2,
solving $F_{i}$ exactly takes time $n^{\operatorname{O}\left(1\right)}\cdot
n^{\operatorname{O}\left(rk\right)}=n^{\operatorname{O}\left(r/\epsilon\right)}$
(since $k=\left\lceil 1/\epsilon\right\rceil$) and uses
$\operatorname{O}\left(\log{n}\right)+\operatorname{O}\left(\sqrt{n}\log{n}\right)+\operatorname{O}\left(rk\log^{2}{n}\right)=\max\left\\{\sqrt{n}\log{n},(r/\epsilon)\log^{2}{n}\right\\}$
bits of space. Finally, each $x=0$ assignment for a variable not appearing in
$F_{1},\dotsc,F_{l}$ costs a single pass over $S_{F}$. It follows that the
total resource costs are $n^{\operatorname{O}\left(r/\epsilon\right)}$ time
and $\max\left\\{\sqrt{n}\log{n},(r/\epsilon)\log^{2}{n}\right\\}$ bits of
space.

We now prove the approximation bound. Let $m$ be the number of clauses in $F$.
Observe that Lemma 1 guarantees any two subformulas $F_{i}$ and $F_{j}$
($i,j\in l$ with $i\neq j$) have no variables in common, and the subformulas
together contain at least $(1-1/k)m\geq(1-\epsilon)m$ clauses of $F$. Thus,
the assignment produced is valid and satisfies at least $(1-\epsilon)m$
clauses, i.e. it is a $(1-\epsilon)$ approximate optimal Planar Max r-SAT
assignment for $F$. ∎

## References

  * [1] Allender, E., Mahajan, M.: The complexity of planarity testing. Information and Computation 189(1), 117–134 (Feb 2004)
  * [2] Asano, T., Kirkpatrick, D., Nakagawa, K., Watanabe, O.: O($\surd$n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. In: Mathematical Foundations of Computer Science. pp. 45–56 (Aug 2014)
  * [3] Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41(1), 153–180 (Jan 1994)
  * [4] Barnes, G., Buss, J.F., Ruzzo, W.L., Schieber, B.: A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. SIAM Journal on Computing 27(5), 1273–1282 (May 1998)
  * [5] Biswas, A., Raman, V., Saurabh, S.: Approximation in (Poly-) Logarithmic Space. Algorithmica 83(7), 2303–2331 (Apr 2021)
  * [6] Chakraborty, D., Tewari, R.: Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs. arXiv Preprint 1502.02135v1 (Feb 2015)
  * [7] Chen, J., Friesen, D.K., Zheng, H.: Tight Bound on Johnson’s Algorithm for Maximum Satisfiability. Journal of Computer and System Sciences 58(3), 622–640 (Jun 1999)
  * [8] Chou, C.N., Golovnev, A., Velusamy, S.: Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT. In: 61st Annual Symposium on Foundations of Computer Science. pp. 330–341 (Nov 2020)
  * [9] Elberfeld, M., Jakoby, A., Tantau, T.: Logspace Versions of the Theorems of Bodlaender and Courcelle. In: 51st Annual Symposium on Foundations of Computer Science. pp. 143–152 (Oct 2010)
  * [10] Elberfeld, M., Kawarabayashi, K.i.: Embedding and canonizing graphs of bounded genus in logspace. In: 46th Annual Symposium on Theory of Computing. pp. 383–392 (May 2014)
  * [11] Frederickson, G.N.: Upper bounds for time-space trade-offs in sorting and selection. Journal of Computer and System Sciences 34(1), 19–26 (Feb 1987)
  * [12] Fredman, M.L., Komlós, J., Szemerédi, E.: Storing a Sparse Table with O(1) Worst Case Access Time. Journal of the ACM 31(3), 538–544 (Jul 1984)
  * [13] Goemans, M.X., Williamson, D.P.: New (3/4)-Approximation Algorithms for the Maximum Satisfiability Problem. SIAM Journal on Discrete Mathematics 7(4), 656–666 (Nov 1994)
  * [14] Izumi, T., Otachi, Y.: Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs. In: 47th International Colloquium on Automata, Languages, and Programming. pp. 67:1 – 67:17 (2020)
  * [15] Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9(3), 256–278 (Dec 1974)
  * [16] Khanna, S., Motwani, R.: Towards a syntactic characterization of PTAS. In: 28th Annual Symposium on Theory of Computing. pp. 329–337 (May 1996)
  * [17] Lieberherr, K.J., Specker, E.: Complexity of Partial Satisfaction. Journal of the ACM 28(2), 411–421 (Apr 1981)
  * [18] Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. Theoretical Computer Science 12(3), 315–323 (Nov 1980)
  * [19] Munro, J.I., Raman, V.: Selection from read-only memory and sorting with minimum data movement. Theoretical Computer Science 165(2), 311–323 (Oct 1996)
  * [20] Reif, J.H.: Symmetric Complementation. Journal of the ACM 31(2), 401–421 (Mar 1984)
  * [21] Reingold, O.: Undirected connectivity in log-space. Journal of the ACM 55(4), 1–24 (Sep 2008)
  * [22] Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B 36(1), 49–64 (Feb 1984)
  * [23] Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences 4(2), 177–192 (Apr 1970)
  * [24] Serna, M.: Approximating linear programming is log-space complete for P. Information Processing Letters 37(4), 233–236 (Feb 1991)
  * [25] Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms (2011)


$\mathcal{V}_{S}(\mu,\nu;\nu_{0})=\exp(\kappa_{S}(\mu,\nu,\nu_{0}))\times\Big{(}\frac{\mu_{E}}{\mu}\Big{)}^{\eta_{S}(\mu,\nu,\nu_{0})}$
(192)

and

$\displaystyle\eta_{S}(\mu,\nu,\nu_{0})$
$\displaystyle=2\Gamma_{\nu}^{S}[\alpha]\ln\left(\frac{\nu}{\nu_{0}}\right),$
$\displaystyle\kappa_{S}(\mu,\nu,\nu_{0})$
$\displaystyle=\Delta\gamma_{\nu}^{s}[\alpha]\ln\left(\frac{\nu}{\nu_{0}}\right),$
(193)

with $\nu_{0}$ the characteristic scale from which we start the evolution.
This scale is chosen such that rapidity logarithms are minimized. The first
term in the rapidity anomalous dimension in Eq.(190) is proportional to the
cusp anomalous dimension and the proportionality constant we denote with
$\xi_{S}$, (i.e. $\Gamma_{\nu}^{S}=\xi_{S}\Gamma_{\text{cusp}}$). The two loop
non-cusp part of the soft rapidity anomalous dimensions which we need for the
NNLL resummation is

$\displaystyle\Delta\gamma_{\nu}^{s}=-\Big{(}\frac{\alpha_{s}(\mu)}{4\pi}\Big{)}^{2}C_{i}\Big{[}\Big{(}\frac{128}{9}-56\zeta_{3}\Big{)}C_{A}+\frac{112}{9}\beta_{0}\Big{]}+\mathcal{O}(\alpha_{s}^{3})\,.$
(194)

##  Appendix C Details for the matching calculation

In this section we give some of the details of the calculations for the
results presented in the main sections. We begin with the calculation of
$d_{D}^{(1)}(\text{antiquak})$ which is presented in Eq. (38). We begin by
expanding one of the propagators in the antiquary line at leading order in
${\boldsymbol{\mathrm{q}}}$ and summing over all possible expansions. After
some simplifications we have

$d_{D}^{(1)}(m,n;\text{antiquark})=-\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\\\
\times\sum_{i=1}^{n}\Big{\\{}\Big{[}g^{i}\prod_{s=i+1}^{n}\frac{A^{0}_{(n+i+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{p}}}^{\prime}_{t}(i)}{2mp_{t}^{{}^{\prime}0}(i)}\Big{[}g^{n-i}\prod_{s=1}^{i}\frac{A^{0}_{(i+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\Big{\\}}v^{(0)}\,.$
(195)

Using Eq. (173) we have

$d_{D}^{(1)}(m,n;\text{antiquark})=-\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\sum_{i=1}^{n}\sum_{\rho=i}^{n}\Big{\\{}\frac{1}{2mp_{t}^{{}^{\prime}0}(\rho)}\\\
\times\Big{[}g^{n-\rho}\prod_{s=\rho+1}^{n}\frac{A^{0}_{(n+\rho+1-s)^{\prime}}}{\sum_{\ell=\rho+1}^{s}p_{\ell}^{{}^{\prime}0}}\Big{]}\Big{[}(-g)^{n-\rho-i}\prod_{s=i+1}^{\rho}\frac{A^{0}_{(\rho+i+1-s)^{\prime}}}{\sum_{\ell=i+1}^{s}p_{\rho+i+1-\ell}^{{}^{\prime}0}}\Big{]}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{p}}}^{\prime}_{t}(i)\Big{[}g^{i}\prod_{s=1}^{i}\frac{A^{0}_{(i+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\Big{\\}}v^{(0)}\,,$
(196)

which after summing over permutations and normalizing correspondingly for each
product and considering all possible values of $n$ and $m$ we have

$d_{D}^{(1)}(\text{antiquark})=-\Big{(}u^{(0)}\Big{)}^{{\dagger}}S_{v}^{{\dagger}}\Gamma^{(0)}S_{v}\Big{[}\frac{1}{2mv\cdot\mathcal{P}}S_{v}^{{\dagger}}\Big{[}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\mathcal{P}}}}S_{v}\Big{]}\Big{]}v^{(0)}\,.$
(197)

This is the result quoted in Eq. (38). We now proceed with the evaluation of
$d_{\gamma}^{(1)}$ which as mentioned earlier is the contribution from the
terms proportional to
${\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}$ from the
expansion of the propagators and spinors. Similar to the case of $d_{D}^{(1)}$
we break down the calculation into expansions along the quark and antiquark
lines:

$d_{\gamma}^{(1)}=d_{\gamma}^{(1)}(\text{quark})+d_{\gamma}^{(1)}(\text{antiquark})\,.$
(198)

Starting with $d_{\gamma}^{(1)}(\text{quark})$ we performed the following
decomposition

$d_{\gamma}^{(1)}(m,n;\text{quark})=d_{\gamma}^{(1)}(m,n;\text{quark})\Big{|}_{u}+\sum_{i=1}^{m}d_{\gamma}^{(1)}(m,n;\text{quark})\Big{|}_{i}$
(199)

corresponding to the expansion of the spinor $\bar{u}(p_{Q})$ and the $i$th
propagator. We then immediately have for the general case $i\neq m$

$d_{\gamma}^{(1)}(m,n;\text{quark})\Big{|}_{i\neq
m}=-(-g)^{m}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}\prod_{s=1}^{i-1}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\frac{\not{A}_{i}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}\not{A}_{i+1}(1+\not{v})}{8mp_{t}^{0}(i)p_{t}^{0}(i+1)}\Big{[}\prod_{s=i+2}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\\\
\times\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(200)

Then using

$\gamma^{\mu_{i}}\;{\boldsymbol{\mathrm{\gamma}}}\;\gamma^{\mu_{i+1}}(1+\not{v})=(1-\not{v})\gamma^{\mu_{i}}\;{\boldsymbol{\mathrm{\gamma}}}\;\gamma^{\mu_{i+1}}+2v^{\mu_{i}}{\boldsymbol{\mathrm{\gamma}}}\;\gamma^{\mu_{i+1}}+2v^{\mu_{i+1}}\gamma^{\mu_{i}}\;{\boldsymbol{\mathrm{\gamma}}}$
(201)

along with the Eq. (170) we have

$d_{\gamma}^{(1)}(m,n;\text{quark})\Big{|}_{i\neq
m}=-(-g)^{m}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}\prod_{s=1}^{i-1}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\frac{A^{0}_{i}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}\not{A}_{i+1}+\not{A}_{i}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}A^{0}_{i+1}}{4mp_{t}^{0}(i)p_{t}^{0}(i+1)}\\\
\times\Big{[}\prod_{s=i+2}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(202)

For the special case $i=m$ we get

$d_{\gamma}^{(1)}(m,n;\text{quark})\Big{|}_{i=m}=-(-g)^{m}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}\prod_{s=1}^{m-1}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\frac{\not{A}_{m}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}}{4mp_{t}^{0}(m)}\\\
\times\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(203)

Expanding the spinor we find

$d_{\gamma}^{(1)}(m,n;\text{quark})\Big{|}_{u}=-(-g)^{m}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}\not{A}_{1}(1+\not{v})}{8mp_{1}^{0}}\prod_{s=2}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\\\
\times\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}$
(204)

and using

$\displaystyle{\boldsymbol{\mathrm{\gamma}}}\;\gamma^{\mu}(1+\not{v})$
$\displaystyle=(1+\not{v})\;{\boldsymbol{\mathrm{\gamma}}}\;\gamma^{\mu}+2v^{\mu}{\boldsymbol{\mathrm{\gamma}}}\;,$
$\displaystyle\Big{(}u^{(0)}\Big{)}^{{\dagger}}(1+\not{v})=2\Big{(}u^{(0)}\Big{)}^{{\dagger}}$
(205)

we have

$d_{\gamma}^{(1)}(m,n;\text{quark})\Big{|}_{u}=-(-g)^{m}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}\not{A}_{1}+{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}A^{0}_{1}}{4mp_{1}^{0}}\prod_{s=2}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\\\
\times\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(206)

Therefore from Eq. (199)we have

$d_{\gamma}^{(1)}(m,n;\text{quark})=-(-g)^{m}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\sum_{i=1}^{m}\Big{\\{}\Big{[}\prod_{s=1}^{i-1}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{A}}}_{i}}{2mp_{t}^{0}(i)}\Big{[}\prod_{s=i+1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Big{\\}}\\\
\times\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\\\
-(-g)^{m}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}}{4m}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(207)

Using Eq. (173):

$d_{\gamma}^{(1)}(m,n;\text{quark})=\Big{(}u^{(0)}\Big{)}^{{\dagger}}\sum_{i=1}^{m}\sum_{\rho=i}^{m}\Big{\\{}\frac{g}{2mp_{t}^{0}(\rho)}\Big{[}(-g)^{i-1}\prod_{s=1}^{i-1}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{A}}}_{i}\\\
\times\Big{[}g^{\rho-i}\prod_{s=i+1}^{\rho}\frac{A^{0}_{s}}{\sum_{\ell=i+1}^{s}p^{0}_{\rho+i+1-\ell}}\Big{]}\Big{[}(-g)^{m-\rho}\prod_{s=\rho+1}^{m}\frac{A^{0}_{s}}{\sum_{\ell=\rho+1}^{s}p^{0}_{\ell}}\Big{]}\Big{\\}}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\\\
\times\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\\\
-\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}}{4m}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(208)

After summing over permutations within each product, normalizing with the
corresponding number of permutations and considering all values of $n$ and $m$
we find

$d_{\gamma}^{(1)}(\text{quark})=+\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}\frac{g}{2mv\cdot\mathcal{P}}S_{v}^{{\dagger}}\,{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{A}}}\,S_{v}\Big{]}S_{v}^{{\dagger}}\Gamma^{(0)}S_{v}v^{(0)}-\Big{(}u^{(0)}\Big{)}^{{\dagger}}S_{v}^{{\dagger}}\,\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}}{4m}\,\Gamma^{(0)}S_{v}v^{(0)}\,.$
(209)

The last element we calculate in this section is
$d_{\gamma}^{(1)}(\text{antiquark})$ which corresponds to the
${\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}$ proportional
terms from the properer and spinor expanding along the antiquark line.
Following similar decomposition as in Eq. (199) we have

$d_{\gamma}^{(1)}(m,n;\text{antiquark})=d_{\gamma}^{(1)}(m,n;\text{antiquark})\Big{|}_{u}+\sum_{i=1}^{m}d_{\gamma}^{(1)}(m,n;\text{antiquark})\Big{|}_{i}$
(210)

where

$d_{\gamma}^{(1)}(m,n;\text{antiquark})\Big{|}_{i}=-g^{n}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\\\
\times\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\sum_{i=1}^{n}\Big{\\{}\Big{[}\prod_{s=i+2}^{n}\frac{A^{0}_{(n+i+2-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\frac{(1-\not{v})\not{A}_{(i+1)^{\prime}}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}\not{A}_{i^{\prime}}}{8mp_{t}^{{}^{\prime}0}(i)p_{t}^{{}^{\prime}0}(i+1)}\Big{[}\prod_{s=1}^{i-1}\frac{A^{0}_{(i-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\Big{\\}}v^{(0)}\,.$
(211)

Then using Eqs. (170) and (201) we rewrite the above as

$d_{\gamma}^{(1)}(m,n;\text{antiquark})\Big{|}_{i\neq
n}=g^{n}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\\\
\times\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}\prod_{s=i+2}^{n}\frac{A^{0}_{(n+i+2-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\frac{\not{A}_{(i+1)^{\prime}}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}A^{0}_{i^{\prime}}+A^{0}_{(i+1)^{\prime}}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}\not{A}_{i^{\prime}}}{4mp_{t}^{{}^{\prime}0}(i)p_{t}^{{}^{\prime}0}(i+1)}\Big{[}\prod_{s=1}^{i-1}\frac{A^{0}_{(i-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(212)

For the special case $i=n$ we have

$d_{\gamma}^{(1)}(m,n;\text{antiquark})\Big{|}_{i\neq
n}=g^{n}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\\\
\times\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}\not{A}_{n}}{4mp_{t}^{{}^{\prime}0}(n)}\Big{[}\prod_{s=1}^{n-1}\frac{A^{0}_{(n-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(213)

Expanding the spinor we get

$d_{\gamma}^{(1)}(m,n;\text{antiquark})\Big{|}_{u}=g^{n}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\\\
\times\Big{[}\prod_{s=2}^{n}\frac{A^{0}_{(n+2-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\frac{(1-\not{v})\not{A}_{1^{\prime}}){\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}}{4mp_{1}^{{}^{\prime}0}}v^{(0)}$
(214)

and using

$\displaystyle(1-\not{v})\gamma^{\mu}\;{\boldsymbol{\mathrm{\gamma}}}$
$\displaystyle=\gamma^{\mu}\;{\boldsymbol{\mathrm{\gamma}}}\;(1-\not{v})-2v^{\nu}\;{\boldsymbol{\mathrm{\gamma}}}\,,$
$\displaystyle(1-\not{v})v^{(0)}$ $\displaystyle=2v^{(0)}$ (215)

we arrive at

$d_{\gamma}^{(1)}(m,n;\text{antiquark})\Big{|}_{u}=g^{n}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\Big{[}\prod_{s=2}^{n}\frac{A^{0}_{(n+2-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\\\
\times\frac{\not{A}_{1^{\prime}}){\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}-A^{0}_{1^{\prime}}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}})}{4mp_{1}^{{}^{\prime}0}}v^{(0)}\,.$
(216)

Adding all contribution from Eq. (210)

$d_{\gamma}^{(1)}(m,n;\text{antiquark})=g^{n}\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\\\
\times\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\sum_{i=1}^{n}\Big{\\{}\Big{[}\prod_{s=i+1}^{n}\frac{A^{0}_{(n+i+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{A}}}_{i^{\prime}}}{2mp_{t}^{{}^{\prime}0}(i)}\Big{[}\prod_{s=1}^{i-1}\frac{A^{0}_{(i-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\Big{\\}}v^{(0)}\\\
-\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}}{4m}\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(217)

Which can be rewritten using Eq. (173)

$d_{D}^{(1)}(m,n;\text{antiquark})=\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\sum_{i=1}^{n}\sum_{\rho=i}^{n}\Big{\\{}\frac{g}{2mp_{t}^{{}^{\prime}0}(\rho)}\\\
\Big{[}g^{n-\rho}\prod_{s=\rho+1}^{n}\frac{A^{0}_{(n+\rho+1-s)^{\prime}}}{\sum_{\ell=\rho+1}^{s}p_{\ell}^{{}^{\prime}0}}\Big{]}\Big{[}(-g)^{n-\rho-i}\prod_{s=i+1}^{\rho}\frac{A^{0}_{(\rho+i+1-s)^{\prime}}}{\sum_{\ell=i+1}^{s}p_{\rho+i+1-\ell}^{{}^{\prime}0}}\Big{]}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{A}}}_{i^{\prime}}\Big{[}g^{i-1}\prod_{s=1}^{i-1}\frac{A^{0}_{(i-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}\Big{\\}}v^{(0)}\\\
-\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{[}(-g)^{m}\prod_{s=1}^{m}\frac{A^{0}_{s}}{p_{t}^{0}(s)}\Big{]}\Gamma^{(0)}(p_{t}(m),p^{\prime}_{t}(n))\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}}{4m}\Big{[}g^{n}\prod_{s=1}^{n}\frac{A^{0}_{(n+1-s)^{\prime}}}{p_{t}^{{}^{\prime}0}(s)}\Big{]}v^{(0)}\,.$
(218)

After summing over permutations within each product, normalizing with the
corresponding number of permutations and considering all values of $n$ and $m$
we obtain

$d_{\gamma}^{(1)}(\text{antiquark})=+\Big{(}u^{(0)}\Big{)}^{{\dagger}}S_{v}^{{\dagger}}\Gamma^{(0)}S_{v}\Big{[}\frac{g}{2mv\cdot\mathcal{P}}S_{v}^{{\dagger}}\,{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{A}}}\,S_{v}\Big{]}v^{(0)}-\Big{(}u^{(0)}\Big{)}^{{\dagger}}S_{v}^{{\dagger}}\Gamma^{(0)}\,\frac{{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{\gamma}}}}{4m}\,S_{v}v^{(0)}\,.$
(219)

From Eqs. (209) and (219) we finally obtain

$d_{\gamma}^{(1)}=\Big{(}u^{(0)}\Big{)}^{{\dagger}}\Big{\\{}S_{v}^{{\dagger}}\Gamma^{(0)}S_{v},\Big{[}\frac{1}{2mv\cdot\mathcal{P}}S_{v}^{{\dagger}}\Big{[}{\boldsymbol{\mathrm{q}}}\cdot{\boldsymbol{\mathrm{A}}}S_{v}\Big{]}\Big{]}-{\boldsymbol{\mathrm{\gamma}}}\Big{\\}}v^{(0)}\,.$
(220)

## References

  * (1) M. G. Echevarria, A. Idilbi and I. Scimemi, _Factorization Theorem For Drell-Yan At Low $q_{T}$ And Transverse Momentum Distributions On-The-Light-Cone_, _JHEP_ 07 (2012) 002, [1111.4996].
  * (2) M. G. Echevarria, A. Idilbi and I. Scimemi, _Unified treatment of the QCD evolution of all (un-)polarized transverse momentum dependent functions: Collins function as a study case_ , _Phys. Rev._ D90 (2014) 014003, [1402.0869].
  * (3) A. Vladimirov, _Structure of rapidity divergences in multi-parton scattering soft factors_ , _JHEP_ 04 (2018) 045, [1707.07606].
  * (4) J. R. Gaunt, _Glauber Gluons and Multiple Parton Interactions_ , _JHEP_ 07 (2014) 110, [1405.2080].
  * (5) X.-d. Ji, J.-p. Ma and F. Yuan, _QCD factorization for semi-inclusive deep-inelastic scattering at low transverse momentum_ , _Phys. Rev._ D71 (2005) 034005, [hep-ph/0404183].
  * (6) STAR collaboration, L. Adamczyk et al., _Measurement of the transverse single-spin asymmetry in $p^{\uparrow}+p\to W^{\pm}/Z^{0}$ at RHIC_, _Phys. Rev. Lett._ 116 (2016) 132301, [1511.06003].
  * (7) COMPASS collaboration, M. Aghasyan et al., _First measurement of transverse-spin-dependent azimuthal asymmetries in the Drell-Yan process_ , _Phys. Rev. Lett._ 119 (2017) 112002, [1704.00488].
  * (8) HERMES collaboration, A. Airapetian et al., _Multiplicities of charged pions and kaons from semi-inclusive deep-inelastic scattering by the proton and the deuteron_ , _Phys. Rev._ D87 (2013) 074029, [1212.5407].
  * (9) COMPASS collaboration, M. Aghasyan et al., _Transverse-momentum-dependent Multiplicities of Charged Hadrons in Muon-Deuteron Deep Inelastic Scattering_ , _Phys. Rev._ D97 (2018) 032006, [1709.07374].
  * (10) Belle collaboration, M. Leitgab et al., _Precision Measurement of Charged Pion and Kaon Differential Cross Sections in e+e- Annihilation at s=10.52 GeV_ , _Phys. Rev. Lett._ 111 (2013) 062002, [1301.6183].
  * (11) BaBar collaboration, J. P. Lees et al., _Production of charged pions, kaons, and protons in $e^{+}e^{-}$ annihilations into hadrons at $\sqrt{s}$=10.54 GeV_, _Phys. Rev._ D88 (2013) 032011, [1306.2895].
  * (12) R. Bain, Y. Makris and T. Mehen, _Transverse Momentum Dependent Fragmenting Jet Functions with Applications to Quarkonium Production_ , _JHEP_ 11 (2016) 144, [1610.06508].
  * (13) D. Neill, I. Scimemi and W. J. Waalewijn, _Jet axes and universal transverse-momentum-dependent fragmentation_ , _JHEP_ 04 (2017) 020, [1612.04817].
  * (14) Y. Makris, _Transverse Momentum Dependent Fragmenting Jet Functions with Applications to Quarkonium Production_ , _PoS_ QCDEV2017 (2017) 035.
  * (15) Z.-B. Kang, X. Liu, F. Ringer and H. Xing, _The transverse momentum distribution of hadrons within jets_ , _JHEP_ 11 (2017) 068, [1705.08443].
  * (16) Y. Makris, D. Neill and V. Vaidya, _Probing Transverse-Momentum Dependent Evolution With Groomed Jets_ , _JHEP_ 07 (2018) 167, [1712.07653].
  * (17) D. Gutierrez-Reyes, I. Scimemi, W. J. Waalewijn and L. Zoppi, _Transverse momentum dependent distributions with jets_ , _Phys. Rev. Lett._ 121 (2018) 162001, [1807.07573].
  * (18) Y. Makris and V. Vaidya, _Transverse Momentum Spectra at Threshold for Groomed Heavy Quark Jets_ , _JHEP_ 10 (2018) 019, [1807.09805].
  * (19) D. Gutierrez-Reyes, I. Scimemi, W. J. Waalewijn and L. Zoppi, _Transverse momentum dependent distributions in $e^{+}e^{-}$ and semi-inclusive deep-inelastic scattering using jets_, 1904.04259.
  * (20) D. Gutierrez-Reyes, Y. Makris, V. Vaidya, I. Scimemi and L. Zoppi, _Probing Transverse-Momentum Distributions With Groomed Jets_ , 1907.05896.
  * (21) A. Accardi et al., _Electron Ion Collider: The Next QCD Frontier_ , _Eur. Phys. J._ A52 (2016) 268, [1212.1701].
  * (22) W. E. Caswell and G. P. Lepage, _Effective Lagrangians for Bound State Problems in QED, QCD, and Other Field Theories_ , _Phys. Lett._ 167B (1986) 437–442.
  * (23) G. T. Bodwin, E. Braaten and G. P. Lepage, _Rigorous QCD analysis of inclusive annihilation and production of heavy quarkonium_ , _Phys. Rev._ D51 (1995) 1125–1171, [hep-ph/9407339].
  * (24) Z.-B. Kang, Y.-Q. Ma, J.-W. Qiu and G. Sterman, _Heavy Quarkonium Production at Collider Energies: Factorization and Evolution_ , _Phys. Rev._ D90 (2014) 034006, [1401.0923].
  * (25) G. C. Nayak, J.-W. Qiu and G. F. Sterman, _Fragmentation, factorization and infrared poles in heavy quarkonium production_ , _Phys. Lett._ B613 (2005) 45–51, [hep-ph/0501235].
  * (26) G. C. Nayak, J.-W. Qiu and G. F. Sterman, _Fragmentation, NRQCD and NNLO factorization analysis in heavy quarkonium production_ , _Phys. Rev._ D72 (2005) 114012, [hep-ph/0509021].
  * (27) Z.-B. Kang, J.-W. Qiu and G. Sterman, _Factorization and quarkonium production_ , _Nucl. Phys. Proc. Suppl._ 214 (2011) 39–43.
  * (28) S. Fleming, A. K. Leibovich, T. Mehen and I. Z. Rothstein, _The Systematics of Quarkonium Production at the LHC and Double Parton Fragmentation_ , _Phys. Rev._ D86 (2012) 094012, [1207.2578].
  * (29) P. L. Cho and A. K. Leibovich, _Color octet quarkonia production_ , _Phys. Rev._ D53 (1996) 150–162, [hep-ph/9505329].
  * (30) P. L. Cho and A. K. Leibovich, _Color octet quarkonia production. 2._ , _Phys. Rev._ D53 (1996) 6203–6217, [hep-ph/9511315].
  * (31) A. Petrelli, M. Cacciari, M. Greco, F. Maltoni and M. L. Mangano, _NLO production and decay of quarkonium_ , _Nucl. Phys._ B514 (1998) 245–309, [hep-ph/9707223].
  * (32) E. Braaten and T. C. Yuan, _Gluon fragmentation into P wave heavy quarkonium_ , _Phys. Rev._ D50 (1994) 3176–3180, [hep-ph/9403401].
  * (33) J. P. Ma, _Quark fragmentation into p wave triplet quarkonium_ , _Phys. Rev._ D53 (1996) 1185–1190, [hep-ph/9504263].
  * (34) E. Braaten and Y.-Q. Chen, _Dimensional regularization in quarkonium calculations_ , _Phys. Rev._ D55 (1997) 2693–2707, [hep-ph/9610401].
  * (35) E. Braaten and S. Fleming, _Color octet fragmentation and the psi-prime surplus at the Tevatron_ , _Phys. Rev. Lett._ 74 (1995) 3327–3330, [hep-ph/9411365].
  * (36) G. T. Bodwin, K.-T. Chao, H. S. Chung, U.-R. Kim, J. Lee and Y.-Q. Ma, _Fragmentation contributions to hadroproduction of prompt $J/\psi$, $\chi_{cJ}$, and $\psi(2S)$ states_, _Phys. Rev._ D93 (2016) 034041, [1509.07904].
  * (37) M. Butenschoen and B. A. Kniehl, _World data of J/psi production consolidate NRQCD factorization at NLO_ , _Phys. Rev._ D84 (2011) 051501, [1105.0820].
  * (38) M. Butenschoen and B. A. Kniehl, _Next-to-leading-order tests of NRQCD factorization with $J/\psi$ yield and polarization_, _Mod. Phys. Lett._ A28 (2013) 1350027, [1212.2037].
  * (39) K.-T. Chao, Y.-Q. Ma, H.-S. Shao, K. Wang and Y.-J. Zhang, _$J/\psi$ Polarization at Hadron Colliders in Nonrelativistic QCD_, _Phys. Rev. Lett._ 108 (2012) 242004, [1201.2675].
  * (40) G. T. Bodwin, H. S. Chung, U.-R. Kim and J. Lee, _Fragmentation contributions to $J/\psi$ production at the Tevatron and the LHC_, _Phys. Rev. Lett._ 113 (2014) 022001, [1403.3612].
  * (41) M. Beneke, I. Z. Rothstein and M. B. Wise, _Kinematic enhancement of nonperturbative corrections to quarkonium production_ , _Phys. Lett._ B408 (1997) 373–380, [hep-ph/9705286].
  * (42) S. Fleming, A. K. Leibovich and T. Mehen, _Resumming the color octet contribution to $e^{+}e^{-}\to J/\psi$ \+ $X$_, _Phys. Rev._ D68 (2003) 094011, [hep-ph/0306139].
  * (43) S. Fleming, A. K. Leibovich and T. Mehen, _Resummation of Large Endpoint Corrections to Color-Octet $J/\psi$ Photoproduction_, _Phys. Rev._ D74 (2006) 114004, [hep-ph/0607121].
  * (44) M. G. Echevarria, _Proper TMD factorization for quarkonia production: $pp\to\eta_{c}$ as a study case_, 1907.06494.
  * (45) Y.-Q. Ma and R. Venugopalan, _Comprehensive Description of $J/\psi$ Production in Proton-Proton Collisions at Collider Energies_, _Phys. Rev. Lett._ 113 (2014) 192301, [1408.4075].
  * (46) Y.-Q. Ma, R. Venugopalan and H.-F. Zhang, _$J/\psi$ production and suppression in high energy proton-nucleus collisions_, _Phys. Rev._ D92 (2015) 071901, [1503.07772].
  * (47) P. Sun, C. P. Yuan and F. Yuan, _Heavy Quarkonium Production at Low $P_{T}$ in NRQCD with Soft Gluon Resummation_, _Phys. Rev._ D88 (2013) 054008, [1210.3432].
  * (48) W. J. den Dunnen, J. P. Lansberg, C. Pisano and M. Schlegel, _Accessing the Transverse Dynamics and Polarization of Gluons inside the Proton at the LHC_ , _Phys. Rev. Lett._ 112 (2014) 212001, [1401.7611].
  * (49) A. Bacchetta, D. Boer, C. Pisano and P. Taels, _Gluon TMDs and NRQCD matrix elements in $J/\psi$ production at an EIC_, 1809.02056.
  * (50) E. L. Berger, J.-w. Qiu and Y.-l. Wang, _Transverse momentum distribution of $\upsilon$ production in hadronic collisions_, _Phys. Rev._ D71 (2005) 034007, [hep-ph/0404158].
  * (51) E. L. Berger, J.-W. Qiu and Y. Wang, _$\upsilon$ transverse momentum at hadron colliders_, _Int. J. Mod. Phys._ A20 (2005) 3753–3755, [hep-ph/0411026].
  * (52) J.-W. Qiu and K. Watanabe, _Heavy quarkonium production in hadronic collisions in TMD framework_ , _PoS_ QCDEV2017 (2017) 024, [1710.06928].
  * (53) C. W. Bauer, S. Fleming and M. E. Luke, _Summing Sudakov logarithms in B — > X(s gamma) in effective field theory_, _Phys. Rev._ D63 (2000) 014006, [hep-ph/0005275].
  * (54) C. W. Bauer, S. Fleming, D. Pirjol and I. W. Stewart, _An Effective field theory for collinear and soft gluons: Heavy to light decays_ , _Phys. Rev._ D63 (2001) 114020, [hep-ph/0011336].
  * (55) C. W. Bauer and I. W. Stewart, _Invariant operators in collinear effective theory_ , _Phys. Lett._ B516 (2001) 134–142, [hep-ph/0107001].
  * (56) C. W. Bauer, D. Pirjol and I. W. Stewart, _Soft collinear factorization in effective field theory_ , _Phys. Rev._ D65 (2002) 054022, [hep-ph/0109045].
  * (57) M. E. Luke, A. V. Manohar and I. Z. Rothstein, _Renormalization group scaling in nonrelativistic QCD_ , _Phys. Rev._ D61 (2000) 074025, [hep-ph/9910209].
  * (58) I. Z. Rothstein, P. Shrivastava and I. W. Stewart, _Manifestly Soft Gauge Invariant Formulation of vNRQCD_ , _Nucl. Phys._ B939 (2019) 405–428, [1806.07398].
  * (59) Y. Makris and I. Vitev, _An Effective Theory of Quarkonia in QCD Matter_ , _JHEP_ 10 (2019) 111, [1906.04186].
  * (60) A. Idilbi and A. Majumder, _Extending Soft-Collinear-Effective-Theory to describe hard jets in dense QCD media_ , _Phys. Rev._ D80 (2009) 054022, [0808.1087].
  * (61) F. D’Eramo, H. Liu and K. Rajagopal, _Transverse Momentum Broadening and the Jet Quenching Parameter, Redux_ , _Phys. Rev._ D84 (2011) 065015, [1006.1367].
  * (62) G. Ovanesyan and I. Vitev, _An effective theory for jet propagation in dense QCD matter: jet broadening and medium-induced bremsstrahlung_ , _JHEP_ 06 (2011) 080, [1103.1074].
  * (63) G. Ovanesyan, _Medium-induced splitting kernels from SCET G_, _Nucl. Phys._ A904-905 (2013) 981c–984c, [1210.4945].
  * (64) M. Benzke, N. Brambilla, M. A. Escobedo and A. Vairo, _Gauge invariant definition of the jet quenching parameter_ , _JHEP_ 02 (2013) 129, [1208.4253].
  * (65) I. Z. Rothstein and I. W. Stewart, _An Effective Field Theory for Forward Scattering and Factorization Violation_ , _JHEP_ 08 (2016) 025, [1601.04695].
  * (66) M. E. Luke and A. V. Manohar, _Reparametrization invariance constraints on heavy particle effective field theories_ , _Phys. Lett._ B286 (1992) 348–354, [hep-ph/9205228].
  * (67) A. V. Manohar, T. Mehen, D. Pirjol and I. W. Stewart, _Reparameterization invariance for collinear operators_ , _Phys. Lett._ B539 (2002) 59–66, [hep-ph/0204229].
  * (68) G. Altarelli, R. K. Ellis, G. Martinelli and S.-Y. Pi, _Processes Involving Fragmentation Functions Beyond the Leading Order in QCD_ , _Nucl. Phys._ B160 (1979) 301–329.
  * (69) E. Braaten and Y.-Q. Chen, _Helicity decomposition for inclusive J / psi production_ , _Phys. Rev._ D54 (1996) 3216–3227, [hep-ph/9604237].
  * (70) J.-y. Chiu, A. Jain, D. Neill and I. Z. Rothstein, _The Rapidity Renormalization Group_ , _Phys. Rev. Lett._ 108 (2012) 151601, [1104.0881].
  * (71) J.-Y. Chiu, A. Jain, D. Neill and I. Z. Rothstein, _A Formalism for the Systematic Treatment of Rapidity Logarithms in Quantum Field Theory_ , _JHEP_ 05 (2012) 084, [1202.0814].
  * (72) I. Scimemi and A. Vladimirov, _Systematic analysis of double-scale evolution_ , _JHEP_ 08 (2018) 003, [1803.11089].
  * (73) J. Collins, D. E. Soper and G. Sterman, _Transverse momentum distribution in drell-yan pair and w and z boson production_ , _Nuclear Physics B_ 250 (1985) 199 – 224.
  * (74) M. Hirai, S. Kumano, T. H. Nagai and K. Sudoh, _Determination of fragmentation functions and their uncertainties_ , _Phys. Rev._ D75 (2007) 094009, [hep-ph/0702250].