# Additive Sparsification of CSPs††thanks: An extended abstract of this work
will appear in the _Proceedings of the 29th European Symposium on Algorithms_
(ESA’21) [29]. Stanislav Živný was supported by a Royal Society University
Research Fellowship. This project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No 714532). The paper reflects only the
authors’ views and not the views of the ERC or the European Commission. The
European Union is not liable for any use that may be made of the information
contained therein.

Eden Pelleg
University of Oxford  Stanislav Živný
University of Oxford

###### Abstract

Multiplicative cut sparsifiers, introduced by Benczúr and Karger [STOC’96],
have proved extremely influential and found various applications. Precise
characterisations were established for sparsifiability of graphs with other
2-variable predicates on Boolean domains by Filtser and Krauthgamer [SIDMA’17]
and non-Boolean domains by Butti and Živný [SIDMA’20].

Bansal, Svensson and Trevisan [FOCS’19] introduced a weaker notion of
sparsification termed “additive sparsification”, which does not require
weights on the edges of the graph. In particular, Bansal et al. designed
algorithms for additive sparsifiers for cuts in graphs and hypergraphs.

As our main result, we establish that _all_ Boolean Constraint Satisfaction
Problems (CSPs) admit an additive sparsifier; that is, for every Boolean
predicate $P:\\{0,1\\}^{k}\to\\{0,1\\}$ of a fixed arity $k$, we show that
CSP($P$) admits an additive sparsifier. Under our newly introduced notion of
all-but-one sparsification for non-Boolean predicates, we show that CSP($P$)
admits an additive sparsifier for _any_ predicate $P:D^{k}\to\\{0,1\\}$ of a
fixed arity $k$ on an arbitrary finite domain $D$.

##  1 Introduction

Graph sparsification is the problem of, given a graph $G=(V,E)$ with
quadratically many (in $|V|$) edges, finding a sparse subgraph
$G_{\varepsilon}=(V,E_{\varepsilon}\subseteq E)$ such that important
properties of $G$ are preserved in $G_{\varepsilon}$. Sparse in this context
usually means with sub-quadratically many edges, though in this work we
require (and can achieve) linearly many edges.

One of the most studied properties of preservation is the size of cuts. If
$G=(V,E,w)$ is an undirected weighted graph with $w:E\to\mathbb{R}_{>0}$,
given some $S\subseteq V$, the cut of $S$ in $G$ is

$\textsf{Cut}_{G}(S)=\sum_{\begin{subarray}{c}\\{u,v\\}\in E\\\ |\\{u,v\\}\cap
S|=1\end{subarray}}w(\\{u,v\\}),$

the sum of weights of all edges connecting $S$ and $S^{c}=V\setminus S$. In an
influential paper, Benczúr and Karger [11] introduced cut sparsification with
a multiplicative error. In particular, [11] showed that for any graph
$G=(V,E,w)$ and any error parameter $0<\varepsilon<1$, there exists a sparse
subgraph $G_{\varepsilon}=(V,E_{\varepsilon}\subseteq E,w^{\prime})$ with
$O(n(\log n)\varepsilon^{-2})$ edges (and new weights $w^{\prime}$ on the
edges in $E_{\varepsilon}$), such that for every $S\subseteq V$ we have

$\textsf{Cut}_{G_{\varepsilon}}(S)\in(1\pm\varepsilon)\textsf{Cut}_{G}(S).$

This was later improved by Batson, Spielman and Srivastava [10] to a subgraph
with $O(n\varepsilon^{-2})$ many edges. Andoni, Chen, Krauthgamer, Qin,
Woodruff and Zhang showed that the dependency on $\varepsilon$ is optimal [4].

The ideas from cut sparsification paved the way to various generalisations,
including streaming [1], sketching [4], cuts in hypergraphs [23, 27], spectral
sparsification [33, 32, 34, 21, 31] and the consideration of other predicates
besides cuts [20]. In this work, we focus on the latter.

The cut sparsification result in [10] was explored for other Boolean binary
predicates by Filtser and Krauthgamer [20], following a suggestion to do so by
Kogan and Krauthgamer in [23]. Filtser and Krauthgamer found [20] a necessary
and sufficient condition on the predicate for the graph to be sparsifiable (in
the sense of [10]). In particular, [20] showed that not all Boolean binary
predicates are sparsifiable. Later, Butti and Živný [14] generalised the
result from [20] to arbitrary finite domain binary predicates.

We remark that [20, 14] use the terminology of _constraint satisfaction
problems_ (CSPs) with a fixed predicate $P$. This is is equivalent to a
(hyper)graph $G$ with a fixed predicate. Indeed, the vertices of $G$
correspond to the variables of the CSP and the (hyper)edges of $G$ correspond
to the constraints of the CSP. If the fixed predicate $P$ is not symmetric,
the (hyper)edges of $G$ are directed. We will mostly talk about sparsification
of (hyper)graphs with a fixed predicate but this is equivalent to the CSP
view.

Recently, while trying to eliminate the requirement for the introduction of
new weights for the sparse subgraph, Bansal, Svensson and Trevisan [7] have
come up with a new sparsification notion with an additive error term. They
have shown (cf. Theorem 3 in Section 2) that under their notion any undirected
unweighted hypergraph has a sparse subhypergraph which preserves all cuts up
to some additive term.

#### Motivation

The relatively recent notion of additive sparsification has not yet been
explored to the same extent as the notion of multiplicative sparsification has
been. We believe that this notion has a lot of potential for applications as
the sparsifiers are not weighted, unlike multiplicative sparsifiers. Indeed,
the main restriction of multiplicative sparsifiers in applications appears to
be the number of distinct weights required in sparsifiers. For some graphs
(such as the “barbell graph” – two disjoint cliques joined by a single edge),
any nontrivial multiplicative sparsifier requires edges of different weights.
In any case, the authors find the notion of additive sparsification
interesting in its own right, independently of applications.

The goal of our work is to understand how the notion of additive
sparsification developed in [7] for cuts behaves on (hyper)graphs with other
predicates (beyond cuts), deriving inspiration from the generalisations of
cuts to other predicates in the multiplicative setting established in [20,
14]. In particular, already Boolean binary predicates include interesting
predicates such as the _uncut edges_ (using the predicate $P(x,y)=1$ iff
$x=y$), _covered edges_ (using the predicate $P(x,y)=1$ iff $x=1$ or $y=1$),
or _directed cut edges_ (using the predicate $P(x,y)=1$ iff $x=0$ and $y=1$).
While such graph problems are well-known and extensively studied, it is not
clear whether one should expect them to be sparsifiable or not. For instance,
as mentioned before, not all (even Boolean binary) predicates are sparsifiable
multiplicatively [20]. Are there some predicates that are not additively
sparsifiable?

###  1.1 Contributions

#### Boolean predicates

Our main result, Theorem 10 in Section 3, shows that _all_ hypergraphs with
_constant_ uniformity $k$, directed or undirected, admit additive
sparsification with respect to all Boolean predicates
$P:\\{0,1\\}^{k}\to\\{0,1\\}$; the number of hyperedges of the sparsifier with
error $\varepsilon>0$ is
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$, where the
$O(\cdot)$ hides a factor that depends on $k$. This result has three
ingredients. First, we observe that the result in [7] also holds true for
directed hypergraphs. Second, we use a reduction via the $k$-partite $k$-fold
covers of hypergraphs to the already solved case of Boolean Cut. Finally, we
use linear algebra to prove the correctness of the reduction. While the
reduction via the $k$-partite $k$-fold cover was used in previous works on
multiplicative sparsification [20, 14], the subsequent non-trivial linear-
algebraic analysis (Proposition 14) is novel and constitutes our main
technical contribution, as well as our result that, unlike in the
multiplicative setting, all Boolean predicates can be (additively) sparsified.
We also show that our results immediately apply to the more general setting
where different hyperedges are associated with different predicates (cf.
Remark 11). This corresponds to CSPs with a fixed constraint language (of a
finite size) rather than just a single predicate.

#### Non-Boolean predicates

We introduce a notion of sparsification that generalises the Boolean case to
predicates on non-Boolean domains, i.e. a notion capturing predicates of the
form $P:D^{k}\to\\{0,1\\}$, where $D$ is an arbitrary fixed finite set with
$|D|\geq 2$. We call this type of sparsification “all-but-one” sparsification
since the additive error term includes the maximum volume of $|D|-1$ (out of
$|D|$) parts, where the volume of a subset is the sum of the degrees in the
subset. (The precise definition can be found in Section 4.) By building on the
techniques used to establish our main result, we show that all hypergraphs
(again, directed or undirected) admit additive all-but-one sparsification with
respect to all predicates. This is stated as Theorem 20 in Section 4. We also
show, in Section 5, that our notion of all-but-one sparsification is, in some
sense, optimal.

#### Comparison to previous work

As mentioned above, our sparsifiability result is obtained by a reduction via
the $k$-partite $k$-fold cover to the cut case established in [7]. A reduction
via the $k$-partite $k$-fold cover was also used (for $k=2$) in previous work
on multiplicative sparsification [20, 14]. In particular, the correctness of
the reduction for Boolean binary predicates in [20] is done via an ad hoc case
analysis for 11 concrete predicates. In the generalisation to binary
predicates on arbitrary finite domains in [14], the correctness is proved via
a combinatorial property of bipartite graphs without a certain $4$-vertex
graph111A bipartite graph on four vertices with each part of size two and
precisely one edge between the two parts. as a subgraph and a reduction to
cuts with more than two parts.

In our case, we use the same black-box reduction via the $k$-partite $k$-fold
cover. Thus the reduction itself is pretty straightforward, although the
analysis is not. In fact, we find it surprising and unexpected that the
$k$-partite $k$-fold cover works in the additive setting. Our key contribution
is the proof of its correctness. A few simple reductions get us to the most
technically involved case, in which $k$ is even and the $k$-ary predicate
satisfies $P(1,\ldots,1)=0$. Additive sparsifiability of such predicates is
established in Proposition 14. Unlike in the multiplicative setting, it is not
clear how to do this in a straightforward way similar to [20, 14]. Instead, we
associate with a given predicate $P$ a vector $v_{P}$ in an appropriate vector
space, identify special vectors that can be shown additively sparsifiable
directly, show that linear combinations preserve sparsifiability, and argue
that $v_{P}$ can be generated by the special vectors. The latter is the most
technical part of the proof. While there are several natural ideas how to
achieve this in a seemingly simpler way (such as arguing that the special
vectors form a basis), we have not managed to produce a simpler or shorter
proof.

The result in [7] also works for non-constant $k$. We emphasise that we deal
with constant $k$, which is standard in the CSP literature in that the
predicate (or a set of predicates) is fixed and not part of the input. For
constant $k$, the representation of predicates is irrelevant (cf. Remark 18).
Thus we do not keep track of (and have not tried to optimise) the precise
dependency of the reduction on the predicate arity $k$ (or the domain size
$q=|D|$).

#### Related work

The already mentioned spectral sparsification [33] is a stronger notion than
cut sparsification as it requires that not only cuts but also the Laplacian
spectrum of a given graph should be (approximately) preserved [32, 34, 21, 31,
7].

Our focus in this article is on _edge sparsifiers_ (of cuts and
generalisations via local predicates). There are also vertex sparsifiers, in
which one reduces the number of vertices. Vertex sparsifiers have been studied
for cut sparsification (between special vertices called terminals) [22, 26,
25, 15] as well as for spectral sparsification [24].

Sparsification in general is about finding a sparse sub(hyper)graph while
preserving important properties of interest. In addition to cut sparsifiers,
another well studied concept is that of _spanners_. A spanner of a graph is a
(sparse) subgraph that approximately preserves distances of shortest paths.
Spanners have been studied in great detail both in the multiplicative [5, 28,
3, 17, 6, 9, 30] and additive [2, 18, 12, 8, 35, 16] setting. Emulators are a
generalisation of spanners in which the sparse graph is not required to be a
subgraph of the original graph. We refer the reader to a nice recent survey of
Elkin and Neimain for more details [19].

##  2 Preliminaries

For an integer $k$, we denote by $[k]$ the set $\\{0,1,\ldots,k-1\\}$. All
graphs and hypergraphs222We use the standard definition of hypergraphs, in
which every hyperedge is an ordered tuple of vertices. in this paper are
unweighted.

For an assignment $a:V\to S$ from the set of vertices of a (hyper)graph to
some set $S$ containing $0$, we denote by $\text{Z}_{a}=\\{v\in V:a(v)=0\\}$
the set of vertices mapped to $0$.

If $0\leq i\leq r^{k}-1$ is an integer, we denote by $\text{rep}_{r,k}(i)$ the
representation of $i$ in base $r$ as a vector in $\mathbb{R}^{k}$, where the
first coordinate stands for the most significant digit, and the last
coordinate for the least significant digit. For the special case $r=2$, we use
the notation $\text{bin}_{k}(i)$ for the binary representation of $i$.

We denote by $v[j]$ the $j$-th coordinate of the vector $v$, counting from
$0$.

For an integer $0\leq i\leq 2^{k}-1$, we use
$\text{zeros}_{k}(i)=\\{\ell\in[k]:\text{bin}_{k}(i)[\ell]=0\\}$; for example
$\text{zeros}_{6}(52)=\\{2,4,5\\}$, since $\text{bin}_{6}(52)=(1,1,0,1,0,0)$.

We now define the value of an assignment on a hypergraph with a fixed
predicate.

######  Definition 1.

Let $G=(V,E)$ be a directed $k$-uniform hypergraph and let
$P:D^{k}\to\\{0,1\\}$ be a $k$-ary predicate on a finite set $D$. Given an
assignment $a:V\to D$ of $G$, the _value_ of $a$ is defined by
$\text{Val}_{G,P}(a)=\sum_{(v_{1},\ldots,v_{k})\in
E}P(a(v_{1}),\ldots,a(v_{k}))$. If $G$ is undirected and $P$ is order
invariant,333$P(b_{1},\ldots,b_{k})=P(b_{\sigma(1)},\ldots,b_{\sigma(k)})$ for
all $b_{1},\ldots,b_{k}\in D$ and every permutation $\sigma$ on the set
$\\{1,\ldots,k\\}$. we define
$\text{Val}_{G,P}(a)=\sum_{\\{v_{1},\ldots,v_{k}\\}\in
E}P(a(v_{1}),\ldots,a(v_{k}))$.444The terms are well defined since $P$ is
order invariant.

The notion of additive sparsification was first introduced in [7] for cuts in
graphs and hypergraphs. In order to define it, we will need the
$\textsf{Cut}:\\{0,1\\}^{k}\to\\{0,1\\}$ predicate defined by
$\textsf{Cut}(b_{1},\ldots,b_{k})=1\iff\exists i,j,b_{i}\neq b_{j}$. Given a
hypergraph $G=(V,E)$ and a set $U\subseteq V$, we denote by
$\text{vol}_{G}(U)$ the _volume_ of $U$, defined as the sum of the degrees in
$G$ of all vertices in $U$.

######  Definition 2.

Let $G=(V,E)$ be an undirected $k$-uniform hypergraph, and denote $|V|=n$. We
say that $G$ _admits additive cut sparsification_ with error $\varepsilon$
using $O(f(n,\varepsilon))$ hyperedges if there exists a subhypergraph
$G_{\varepsilon}=(V,E_{\varepsilon}\subseteq E)$ with
$|E_{\varepsilon}|=O(f(n,\varepsilon))$, called an _additive sparsifier_ of
$G$, such that for every assignment $a:V\to\\{0,1\\}$ we have

$\left|\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a)-\text{Val}_{G,\textsf{Cut}}(a)\right|\leq\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})),$
(1)

where $d_{G}$ is the average degree of $G$.

Note that (1) can also be written as

$\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a)\in\text{Val}_{G,\textsf{Cut}}(a)\pm\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})),$

which explains the use of the term “additive” for the error.

Bansal, Svensson and Trevisan [7] showed the following sparsification result:

######  Theorem 3 (Additive Cut Sparsification [7, Theorem 1.3]).

Let $G=(V,E)$ be an undirected $n$-vertex $k$-uniform hypergraph, and
$\varepsilon>0$. Then $G$ admits additive cut sparsification with error
$\varepsilon$ using
$O\left(\frac{n}{k}\varepsilon^{-2}\log(\frac{k}{\varepsilon})\right)$
hyperedges.

######  Remark 4.

We call a predicate $P$ _symmetric_ if it is order invariant (as in Definition
1). Since Theorem 3 deals with only _undirected_ hypergraphs, it is not clear
how to generalise it to non-symmetric predicates directly, since the value of
such predicates on undirected hypergraphs is not defined. Therefore, our
course of action will be first to prove it for the case of directed
hypergraphs, and then generalise it to other predicates on directed
hypergraphs. In fact, by doing this we also prove the result for undirected
hypergraphs with symmetric predicates, since hyperedges can be given arbitrary
directions without changing the average degree of $G$, or the volume in $G$,
or the value of the predicate in any assignment.

######  Remark 5.

Throughout this paper we only discuss the existence of sparsifiers and do not
mention the time complexity to find them. However, the (implicit) time
complexity results from [7] apply in our more general setting as well since
the sparsifiers we find are in fact the same sparsifiers for all predicates,
including cuts (cf. Remark 17).

An important tool we use to prove our results is the $k$-partite $k$-fold
cover of a hypergraph. This construction is a well known one, and has been
used for multiplicative sparsification (for $k=2$) in [20] and [14].

######  Definition 6.

Let $G=(V,E)$ be a directed $k$-uniform hypergraph. The _$k$ -partite $k$-fold
cover_ of $G$ is the hypergraph $\gamma(G)=(V^{\gamma},E^{\gamma})$ where

$V^{\gamma}=\\{v^{(0)},v^{(1)},\ldots,v^{(k-1)}:v\in V\\},$
$E^{\gamma}=\\{(v_{1}^{(0)},v_{2}^{(1)},\ldots,v_{k}^{(k-1)}):(v_{1},\ldots,v_{k})\in
E\\}.$

If $G$ is undirected we define the cover in the same way except

$E^{\gamma}=\\{\\{v_{1}^{(0)},v_{2}^{(1)},\ldots,v_{k}^{(k-1)}\\}:\\{v_{1},\ldots,v_{k}\\}\in
E\\},$

so for each hyperedge in $G$ we get $k!$ hyperedges in $\gamma(G)$ in this
case.

If $k=2$ then $\gamma(G)$ corresponds to the well-known _bipartite double
cover_ of $G$ [13].

##  3 Sparsification of Boolean Predicates

As mentioned in Section 1, we begin by observing that Theorem 3 also works for
directed hypergraphs. (We emphasise that we treat $k$ as a constant, cf.
Remark 18.)

We will need a notation for the undirected equivalent of a directed
hypergraph.

######  Definition 7.

Given a directed $k$-uniform hypergraph $G=(V,E)$, the _undirected equivalent_
of $G$ is $\Lambda(G)=(V,\overline{E})$ where
$\overline{E}=\\{\\{v_{1},\ldots,v_{k}\\}:(v_{1},\ldots,v_{k})\in E\\}$.

In other words, $\Lambda(G)$ is obtained by “forgetting” the directions of the
hyperedges of $G$ (and ignoring duplicates if they exist).

######  Proposition 8.

Let $G=(V,E)$ be a directed $n$-vertex $k$-uniform hypergraph, and
$\varepsilon>0$. Then $G$ admits additive cut sparsification with error
$\varepsilon$ using $O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$
hyperedges.

###### Proof.

Let $\varepsilon>0$, and let $\gamma(G)=(V^{\gamma},E^{\gamma})$ be the
$k$-partite $k$-fold cover of $G$. Let $\Lambda(\gamma(G))$ be the undirected
equivalent of $\gamma(G)$. Let
$\Lambda(\gamma(G))_{\varepsilon}=(V^{\gamma}_{\varepsilon},\overline{E^{\gamma}_{\varepsilon}})$
be a subhypergraph of $\Lambda(\gamma(G))$ promised by Theorem 3. By the
construction of the $k$-partite $k$-fold cover, there are no two directed
hyperedges over the same set of vertices, and so there is a 1-1 correspondence
between the hyperedges of $G$ and the hyperedges of $\Lambda(\gamma(G))$.
Hence we have a subhypergraph $G_{\varepsilon}=(V,E_{\varepsilon})$ of $G$
such that $\Lambda(\gamma(G_{\varepsilon}))=\Lambda(\gamma(G))_{\varepsilon}$
(by taking the hyperedges corresponding to the ones of
$\Lambda(\gamma(G))_{\varepsilon}$). We also have
$|\overline{E^{\gamma}}|=|E|$ and
$|\overline{E^{\gamma}_{\varepsilon}}|=|E_{\varepsilon}|$.

Let $a:V\to\\{0,1\\}$. Define $a^{\prime}:V^{\gamma}\to\\{0,1\\}$ by
$a^{\prime}(v^{(i)})=a(v)$. We have

$\text{Val}_{G,\textsf{Cut}}(a)=\text{Val}_{\Lambda(\gamma(G)),\textsf{Cut}}(a^{\prime}),$
(2)

which is true for any hypergraph, and in particular for $G_{\varepsilon}$:

$\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a)=\text{Val}_{\Lambda(\gamma(G_{\varepsilon})),\textsf{Cut}}(a^{\prime}).$
(3)

Applying Theorem 3 to $\Lambda(\gamma(G))$ and $a^{\prime}$ gives us

$\displaystyle\left|\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a)-\text{Val}_{G,\textsf{Cut}}(a)\right|$
$\displaystyle=\left|\frac{|\overline{E^{\gamma}}|}{|\overline{E^{\gamma}_{\varepsilon}}|}\text{Val}_{\Lambda(\gamma(G_{\varepsilon})),\textsf{Cut}}(a^{\prime})-\text{Val}_{\Lambda(\gamma(G)),\textsf{Cut}}(a^{\prime})\right|$
$\displaystyle\leq\varepsilon(d_{\Lambda(\gamma(G))}\left|\text{Z}_{a^{\prime}}\right|+\text{vol}_{\Lambda(\gamma(G))}(\text{Z}_{a^{\prime}}))$
$\displaystyle=\varepsilon(d_{\gamma(G)}\cdot
k|\text{Z}_{a}|+\text{vol}_{\gamma(G)}(\text{Z}_{a^{\prime}}))$
$\displaystyle=\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})),$

where the first line is due to (2) and (3), the second line is by Theorem 3,
and the last two lines are by properties of the $k$-partite $k$-fold cover.
Moreover

$|E_{\varepsilon}|=|\overline{E^{\gamma}_{\varepsilon}}|=O\left(\frac{kn}{k}\varepsilon^{-2}\log\frac{k}{\varepsilon}\right)=O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right),$

as required. ∎

From now on, whenever we say a “hypergraph”, we mean a “directed hypergraph”
with $n$ vertices. By Remark 4, the results also apply to undirected
hypergraphs (whenever it makes sense, i.e. if the associated predicate is
symmetric). We also omit the word additive when discussing sparsification. The
following notion of sparsification is a natural generalisation of cut
sparsification (Definition 2) to arbitrary predicates.

######  Definition 9.

Let $P$ be a $k$-ary Boolean predicate and $G=(V,E)$ a $k$-uniform hypergraph.
We say that $G$ _admits $P$-sparsification_ with error $\varepsilon$ using
$O(f(n,\varepsilon))$ hyperedges if there exists a subhypergraph
$G_{\varepsilon}=(V,E_{\varepsilon}\subseteq E)$ with
$|E_{\varepsilon}|=O(f(n,\varepsilon))$, called a _$P$ -sparsifier_ of $G$,
such that for every assignment $a:V\to\\{0,1\\}$ we have

$\left|\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},P}(a)-\text{Val}_{G,P}(a)\right|\leq\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})),$
(4)

where $d_{G}$ is the average degree of $G$.

The following theorem is our main result, extending Proposition 8 to _all_
$k$-ary predicates with Boolean domains.

######  Theorem 10 (Main).

For every $k$-uniform hypergraph $G$ ($k$ is a constant), every $k$-ary
Boolean predicate $P:\\{0,1\\}^{k}\to\\{0,1\\}$, and every $\varepsilon>0$,
$G$ admits $P$-sparsification with error $\varepsilon$ using
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$ hyperedges.

Theorem 10 can be informally restated as “ _every $k$-uniform hypergraph is
sparsifiable with respect to all $k$-ary Boolean predicates_” or “ _for every
Boolean predicate $P$ of constant arity, CSP($P$) is sparsifiable_”.

######  Remark 11.

It is possible to consider an even more general case where each hyperedge in
$G$ has its own predicate. In this case, we can apply Theorem 10 to each of
the hypergraphs obtained by taking only hyperedges corresponding to a specific
predicate, and so get a sparsifier for each such predicate. Taking the union
of all their hyperedges, we get a new hypergraph $G_{\varepsilon}$, which is a
sparsifier of the original hypergraph. Indeed, it has
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$ hyperedges since it
is the union of a constant number of hypergraphs. (The number of predicates
$P:\\{0,1\\}^{k}\to\\{0,1\\}$ is constant, since $k$ is constant.) It also
satisfies (4) for any given assignment up to some constant factor, since all
the sparsifiers it is composed of do. This constant factor can be eliminated
by choosing $\varepsilon_{0}=\frac{\varepsilon}{m}$ for an appropriate $m$
that depends only on $k$.

The main work in the proof of Theorem 10 is for even values of $k$; a simple
reduction (Proposition 16) then reduces the case of $k$ odd to the even case.

In order to prove Theorem 10 for even $k$, we use the $k$-partite $k$-fold
cover of $G$ and apply Proposition 8 to various assignments of it. For a
$k$-ary Boolean predicate $P:\\{0,1\\}^{k}\to\\{0,1\\}$, we consider the
vector $v_{P}\in\mathbb{R}^{2^{k}}$, defined by
$v_{P}[i]=P(\text{bin}_{k}(i))$. For instance, for the Cut predicate on a
3-uniform hypergraph, we have $v_{\textsf{Cut}}=(0,1,1,1,1,1,1,0)$.

For a given hypergraph $G$ and an assignment $a$, we consider the vector
$v_{G,a}\in\mathbb{R}^{2^{k}}$ defined by
$v_{G,a}[i]=\left|\\{(v_{1},\ldots,v_{k})\in
E:(a(v_{1}),\ldots,a(v_{k}))=\text{bin}_{k}(i)\\}\right|$. In other words,
each coordinate of $v_{G,a}$ counts the hyperedges in $G$ whose vertices are
assigned some specific set of values by $a$.

######  Example 12.

Given the graph $G=(V,E)$ in Figure 1 (so $k=2$) and the assignment
$a:V\to\\{0,1\\}$ defined as $a(v_{1})=a(v_{2})=a(v_{3})=0$ and
$a(v_{4})=a(v_{5})=a(v_{6})=a(v_{7})=1$, we have $v_{G,a}=(2,3,1,5)$, since
there are two edges with assignment $(0,0)$, namely $(v_{1},v_{2})$ and
$(v_{2},v_{3})$, three edges with assignment $(0,1)$, namely $(v_{1},v_{4})$,
$(v_{2},v_{6})$, and $(v_{2},v_{7})$, etc.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$ Figure 1: Graph from Example
12.

Under these notations, we get $\text{Val}_{G,P}(a)=\langle
v_{P},v_{G,a}\rangle$, where $\langle\cdot,\cdot\rangle$ is the standard inner
product in $\mathbb{R}^{2^{k}}$. We begin by proving the following useful
lemma.

######  Lemma 13.

Let $G=(V,E)$ be a $k$-uniform hypergraph, $P_{1},\ldots,P_{m}$ be $k$-ary
Boolean predicates ($m$ is a constant). Suppose that for every $\varepsilon>0$
and $1\leq i\leq m$, $G$ admits $P_{i}$-sparsification with error
$\varepsilon$ using $O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$
hyperedges, and that the same subhypergraph
$G_{\varepsilon}=(V,E_{\varepsilon}\subseteq E)$ is a $P_{i}$-sparsifier for
all $P_{i}$. Suppose that $P$ is some $k$-ary Boolean predicate for which we
have $v_{P}=\sum_{i=1}^{m}\lambda_{i}v_{P_{i}}$ for some constants
$\lambda_{1},\ldots,\lambda_{m}\in\mathbb{R}$. Under these conditions, $G$
admits $P$-sparsification with error $\varepsilon$ using
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$ hyperedges.

###### Proof.

Let $\varepsilon>0$ and denote
$\varepsilon_{i}=\frac{\varepsilon}{m|\lambda_{i}|}$ (if $\lambda_{i}=0$ take
$\varepsilon_{i}=1$ instead) and
$\varepsilon_{0}=\min\\{\varepsilon_{1},\ldots,\varepsilon_{m}\\}$. Let
$G_{\varepsilon_{0}}=(V,E_{\varepsilon_{0}})$ be the common witness
subhypergraph for $\varepsilon_{0}$ promised by the assumption. We know that
every $P_{i}$ satisfies

$\left|\frac{|E|}{|E_{\varepsilon_{0}}|}\text{Val}_{G_{\varepsilon_{0}},P_{i}}(a)-\text{Val}_{G,P_{i}}(a)\right|\leq\varepsilon_{0}(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a}))$
(5)

for every assignment $a:V\to\\{0,1\\}$. We also have

$\text{Val}_{G,P}(a)=\langle
v_{P},v_{G,a}\rangle=\left\langle\sum_{i=1}^{m}\lambda_{i}v_{P_{i}},v_{G,a}\right\rangle=\sum_{i=1}^{m}\lambda_{i}\langle
v_{P_{i}},v_{G,a}\rangle=\sum_{i=1}^{m}\lambda_{i}\text{Val}_{G,P_{i}}(a),$

and similarly

$\text{Val}_{G_{\varepsilon_{0}},P}(a)=\sum_{i=1}^{m}\lambda_{i}\text{Val}_{G_{\varepsilon_{0}},P_{i}}(a).$

Therefore, for every assignment $a$ we get

$\displaystyle\left|\frac{|E|}{|E_{\varepsilon_{0}}|}\text{Val}_{G_{\varepsilon_{0}},P}(a)-\text{Val}_{G,P}(a)\right|$
$\displaystyle=\left|\frac{|E|}{|E_{\varepsilon_{0}}|}\sum_{i=1}^{m}\lambda_{i}\text{Val}_{G_{\varepsilon_{0}},P_{i}}(a)-\sum_{i=1}^{m}\lambda_{i}\text{Val}_{G,P_{i}}(a)\right|$
$\displaystyle\leq\sum_{i=1}^{m}|\lambda_{i}|\left|\frac{|E|}{|E_{\varepsilon_{0}}|}\text{Val}_{G_{\varepsilon_{0}},P_{i}}(a)-\text{Val}_{G,P_{i}}(a)\right|$
$\displaystyle\leq\sum_{i=1}^{m}|\lambda_{i}|\varepsilon_{0}(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a}))$
$\displaystyle\leq\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})),$

where the second line is due to the triangle inequality, the third is due to
(5) and the fourth is by the definition of $\varepsilon_{0}$.

Furthermore, since $m$ and all $\lambda_{i}$ are constants,

$|E_{\varepsilon_{0}}|=O\left(n\varepsilon_{0}^{-2}\log\frac{1}{\varepsilon_{0}}\right)=O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right),$

and so $G_{\varepsilon_{0}}$ is a witness for the $P$-sparsification of $G$. ∎

The core of the proof of Theorem 10 is in the next proposition, which
establishes the result for Boolean predicates on even uniformity hypergraphs,
with a small restriction.

######  Proposition 14.

Let $k$ be an even number and $G$ be a $k$-uniform hypergraph. Let $P$ be a
$k$-ary Boolean predicate with $P(1,1,\ldots,1)=0$. Then for every
$\varepsilon>0$, $G$ admits $P$-sparsification with error $\varepsilon$ using
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$ hyperedges.

###### Proof.

Let $\varepsilon>0$. We consider $\gamma(G)$, the $k$-partite $k$-fold cover
of $G$. Let $\gamma(G)_{\varepsilon}$ be a subhypergraph of $\gamma(G)$
promised by Proposition 8, and $G_{\varepsilon}=(V,E_{\varepsilon})$ the
corresponding subhypergraph of $G$, i.e. the subhypergraph which satisfies
$\gamma(G_{\varepsilon})=\gamma(G)_{\varepsilon}$ (by taking the hyperedges
corresponding to the ones of $\gamma(G)_{\varepsilon}$).

Let $a:V\to\\{0,1\\}$. For every subset $T\subseteq[k]$, we look at the
assignment $a_{T}:V^{\gamma}\to\\{0,1\\}$ defined by $a_{T}(v^{(i)})=0$ if
$i\in T$ and $a(v)=0$, and $a_{T}(v^{(i)})=1$ otherwise. We therefore have

$\left|\frac{|E^{\gamma}|}{|E^{\gamma}_{\varepsilon}|}\text{Val}_{\gamma(G)_{\varepsilon},\textsf{Cut}}(a_{T})-\text{Val}_{\gamma(G),\textsf{Cut}}(a_{T})\right|\leq\varepsilon(d_{\gamma(G)}|\text{Z}_{a_{T}}|+\text{vol}_{\gamma(G)}(\text{Z}_{a_{T}})).$
(6)

Define the vector $u_{T}\in\mathbb{R}^{2^{k}}$ as follows:

$u_{T}[j]=\left\\{\begin{array}[]{lr}1&\qquad
T\cap\text{zeros}(j)\neq\emptyset,[k]\\\ 0&\qquad
otherwise\end{array}\right..$

In other words, the vector $u_{T}$ is 1 in index $j$ if and only if there
exists an index $i\in T$ in which the binary representation of $j$ has a zero,
with the exception of $u_{[k]}[0]=0$. Denote by $P_{T}$ the predicate
corresponding to $u_{T}$, that is $P_{T}(\text{bin}_{k}(j))=1\iff u_{T}[j]=1$.
Observe that

$\text{Val}_{\gamma(G),\textsf{Cut}}(a_{T})=\text{Val}_{G,P_{T}}(a),$

since they both count exactly hyperedges $(v_{1},\ldots,v_{k})$ which have
some vertex $v_{i}$ with $a(v_{i})=0$ with $i\in T$, but if $T=[k]$ then they
do not count hyperedges which have $a(v_{i})=0$ for all $i=1,\ldots,k$ (see
example in Figure 2). The same is true for any hypergraph, and in particular
for $G_{\varepsilon}$, that is

$\text{Val}_{\gamma(G_{\varepsilon}),\textsf{Cut}}(a_{T})=\text{Val}_{G_{\varepsilon},P_{T}}(a).$

Putting these results in (6), we get

$\displaystyle\left|\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},P_{T}}(a)-\text{Val}_{G,P_{T}}(a)\right|$
$\displaystyle\leq\varepsilon(d_{\gamma(G)}|\text{Z}_{a_{T}}|+\text{vol}_{\gamma(G)}(\text{Z}_{a_{T}}))$
$\displaystyle\leq\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})),$

so $G$ admits $P_{T}$ sparsification with error $\varepsilon$ using
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$ hyperedges for
every $T\subseteq[k]$, and for every $\varepsilon$ the sparsification is
witnessed by the same subhypergraph $G_{\varepsilon}$. (Notice that
Proposition 8, when applied to $\gamma(G)$ which has $kn$ vertices, gives us a
subhypergraph with $O\left(kn\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$
hyperedges, and recall that $k$ is a constant.)

$\text{Z}_{a}^{(0)}$$\overline{\text{Z}}_{a}^{(0)}$$\text{Z}_{a}^{(1)}$$\overline{\text{Z}}_{a}^{(1)}$$\text{Z}_{a}^{(2)}$$\overline{\text{Z}}_{a}^{(2)}$$\text{Z}_{a}^{(3)}$$\overline{\text{Z}}_{a}^{(3)}$$\text{Z}_{a}^{(4)}$$\overline{\text{Z}}_{a}^{(4)}$$\ldots$$\text{Z}_{a}^{(k-2)}$$\overline{\text{Z}}_{a}^{(k-2)}$$\text{Z}_{a}^{(k-1)}$$\overline{\text{Z}}_{a}^{(k-1)}$
Figure 2: An example of a representation of an assignment on $\gamma(G)$.
$\text{Z}_{a}^{(i)}$ consists of all vertices in $V^{(i)}$ which are a copy of
a vertex $v\in V$ with $a(v)=0$, and $\overline{\text{Z}}_{a}^{(i)}$ consists
of the rest of $V^{(i)}$. Each hyperedge has a unique path from left to right
(but a path might belong to multiple hyperedges), choosing one of
$\text{Z}_{a}^{(i)},\overline{\text{Z}}_{a}^{(i)}$ for each $i$. Each such
path is also in 1-1 correspondence with a coordinate in $u_{T}$. In this
example $T=\\{0,3,k-1\\}$ and the shaded sets represent $a_{T}^{-1}(0)$. By
green dotted lines we indicated a path corresponding to a hyperedge counted in
$\text{Val}_{\gamma(G),\textsf{Cut}}(a_{T})$, and by red dashed lines we
indicated a path which does not. The green dotted path corresponds to a value
of $1$ in the coordinate of $u_{T}$ with binary representation
$(1,1,0,0,1,\ldots,0,1)$, and the red dashed path to a value $0$ in the
coordinate with binary representation $(1,0,1,1,0,,\ldots,1,1)$. Note that if
$T=[k]$ then any hyperedge corresponding to a path only on
$\text{Z}_{a}^{(i)}$ is not counted.

Our next goal is to show that the vector $v_{P}$ is a linear combination of
the vectors $u_{T}$ for all $T\in[k]$. To show that, we show that every vector
$e_{r}$ in the standard basis of $\mathbb{R}^{2^{k}}$, with $r\neq 2^{k}-1$,
is a linear combination of these vectors. This is sufficient since the last
coordinate of $v_{P}$ is 0 by the assumption. First we need to order the
various sets $T$. We order them in the following decreasing lexicographic
order $T_{0},T_{1},\ldots,T_{2^{k}-1}$, where $T_{j}=\text{zeros}(j)$, so
$T_{0}=[k],T_{1}=[k]\setminus\\{k-1\\},T_{2}=[k]\setminus\\{k-2\\},T_{3}=[k]\setminus\\{k-1,k-2\\},T_{4}=[k]\setminus\\{k-3\\}$
and so on, until $T_{2^{k}-1}=\emptyset$.

Let $e_{r}$ be a vector in the standard basis of $\mathbb{R}^{2^{k}}$. We
introduce the following coefficients for $0\leq m\leq 2^{k}-1$:

$\lambda_{r,m}=\frac{1}{2}(-1)^{\text{Ham}(r\oplus m)+(1-\mathds{1}_{r\&m})},$

where $\oplus,\&$ are the Xor and And binary functions respectively,555The Xor
of two integers is defined as the bitwise Boolean Xor of their binary
representations, where the Boolean Xor of two bits is their sum modulo 2. The
And of two integers is defined the same way with the Boolean And function
which is defined as And$(i,j)=1\iff i=j=1$. Ham is the Hamming weight
function, and $\mathds{1}_{d}$ returns 1 if $d\neq 0$ and 0 if $d=0$. Denote

$f_{1}(m)=\text{Ham}(r\oplus m)\quad,\quad f_{2}(m)=(1-\mathds{1}_{r\&m}).$

We shall prove that

$e_{r}=\sum_{m=0}^{2^{k}-1}\lambda_{r,m}u_{T_{m}}.$ (7)

We start with a claim.

Claim: The sum of all coefficients is 0; i.e.,
$\sum_{m=0}^{2^{k}-1}\lambda_{r,m}=0$.

_Proof of the claim_. Let $b_{1}b_{2}\ldots b_{k}$ be the binary
representation of $r$. Since $r<2^{k}-1$, there exists some $1\leq i\leq r$
for which $b_{i}=0$. We can partition the coefficients into pairs, such that
$\lambda_{r,m_{1}},\lambda_{r,m_{2}}$ is a pair if and only if $m_{1},m_{2}$
differ in the $i$-th coordinate only. This is clearly a partition. For each
pair, $f_{1}$ gives $m_{1},m_{2}$ different parity values, and $f_{2}$ gives
them the same value (since $b_{i}=0$), so
$\lambda_{r,m_{1}},\lambda_{r,m_{2}}$ have opposite signs, so their sum is
zero. This is true for every pair, so the overall sum is zero, and the claim
is proved. _(End of the the proof of the claim.)_

We prove (7) coordinate-wise. First we look at the coordinate $r$. Consider
the set $W$ of all vectors $u_{T_{m}}$ for which the coordinate $r$ is 0. If
we show that the sum of the corresponding coefficients of the vectors in $W$
is $-1$, using the claim we will deduce the result in this case. We
distinguish 2 cases:

Case (I): $r=0$. By the definition of $u_{T}$, in this case the set $W$
contains two vectors, $u_{[k]}$ and $u_{\emptyset}$. The corresponding
coefficients are $\lambda_{r,0}=-\frac{1}{2}$ and
$\lambda_{r,2^{k}-1}=-\frac{1}{2}$ (since $k$ is even), which sum up to $-1$.

Case (II): $r>0$. As in the proof of the claim, let $b_{1}b_{2}\ldots b_{k}$
be the binary representation of $r$, and choose a coordinate $1\leq i\leq k$
for which $b_{i}=1$. Partition the vectors in $W$ into pairs where
$u_{T_{m_{1}}},u_{T_{m_{2}}}$ is a pair if and only if $m_{1},m_{2}$ differ in
the $i$-th coordinate only. This is clearly a partition of all vectors, and by
the definition of $u_{T}$, each such pair is either contained in $W$ or
disjoint from $W$ so this is indeed a partition of $W$. (Note that
$u_{T_{m_{1}}}[r]$ is determined by $T_{m_{1}}\cap\text{zeros}(r)$ which is in
fact $\text{zeros}(m_{1})\cap\text{zeros}(r)$, and the same for $m_{2}$. Since
$m_{1},m_{2}$ differ in the $i$-th coordinate only, and $r$ is not zero in
this coordinate, this coordinate contributes nothing to the intersections, and
so both these intersections are empty or non-empty together. The intersection
never equals $[k]$ since $r>0$.) For every such pair in $W$, if it does not
contain the negation of bin$(r)$, then there is some other index $j\neq i$ in
which $r,m_{1},m_{2}$ are all 1\. (This is because in all other coordinates
$m_{1},m_{2}$ are equal, and since they are not the negation of $r$, there is
some coordinate $j\neq i$ in which they are equal to the $j$-th coordinate of
$r$. These coordinates cannot be all 0, since this would imply
$u_{T_{m_{1}}},u_{T_{m_{2}}}\notin W$.) This implies that $f_{2}$ gives
$m_{1},m_{2}$ the same value, and clearly $f_{1}$ gives them different parity
values, so $\lambda_{r,m_{1}}+\lambda_{r,m_{2}}=0$. However, for the pair
which contains the negation of $r$ (this pair is clearly in $W$), suppose
without loss of generality the negation is $m_{1}$. Then $f_{2}$ gives
$m_{1},m_{2}$ the values $1,0$ respectively, and $f_{1}$ gives $m_{1}$ an even
value and $m_{2}$ an odd value (since $k$ is even), and so
$\lambda_{r,m_{1}}=\lambda_{r,m_{2}}=-\frac{1}{2}$, and the overall sum is
$-1$. This finishes the proof of (7) in the coordinate $r$.

Now let $r^{\prime}\neq r$ be some other coordinate, and let $c_{1}c_{2}\ldots
c_{k}$ be its binary representation. First, if $r^{\prime}=2^{k}-1$ then for
all $m$ we have $u_{T_{m}}[r^{\prime}]=0$ by definition, so the linear
combination of this coordinate is 0. So suppose $r^{\prime}<2^{k}-1$. As
before let $W$ be the set of all vectors $u_{T_{m}}$ for which the coordinate
$r^{\prime}$ is 0. We show that the sum of the corresponding coefficients is
zero, and again deduce the result using the claim. Now, there exists some
index $i$ for which $b_{i}\neq c_{i}$. Again we have two cases:

Case (1): $b_{i}=0,c_{i}=1$. Partition the vectors in $W$ into pairs where
$u_{T_{m_{1}}},u_{T_{m_{2}}}$ is a pair if and only if $m_{1},m_{2}$ differ in
the $i$-th coordinate only. This is clearly a partition of all the vectors,
and by the definition of $u_{T}$, each such pair is either contained in $W$ or
disjoint from $W$, so this is indeed a partition of $W$. For every such pair
in $W$, $f_{1}$ gives $m_{1},m_{2}$ different parity values, and $f_{2}$ gives
them the same value (since $b_{i}=0$), so
$\lambda_{r,m_{1}},\lambda_{r,m_{2}}$ have opposite signs, so their sum is
zero. This is true for every pair in $W$, so the overall sum is zero.

Case (2) $b_{i}=1,c_{i}=0$. Here we consider two sub-cases:

Case (2a): $r^{\prime}=0$. The only vectors in $W$ in this case are $u_{[k]}$
and $u_{\emptyset}$. The corresponding coefficients are
$\lambda_{r,0}=\frac{1}{2}(-1)^{\text{Ham}(r)+1}$ and
$\lambda_{r,2^{k}-1}=\frac{1}{2}(-1)^{\text{Ham}(\neg r)}$, where $\neg r$
denotes the negation of the binary representation of $r$. Since $k$ is even,
we know that $r,\neg r$ have the same parity, and so the sum of the two
coefficients is 0.

Case (2b): $r^{\prime}\neq 0$. Choose some $j$ for which $c_{j}=1$. Partition
the vectors in $W$ into pairs where $u_{T_{m_{1}}},u_{T_{m_{2}}}$ is a pair if
and only if $m_{1},m_{2}$ differ in the $j$-th coordinate only. The argument
for this being a partition of $W$ is similar to the argument in Case (1). For
each pair in $W$, $f_{1}$ gives $m_{1},m_{2}$ a different parity as always,
and $f_{2}$ gives them the same value, since $r,m_{1},m_{2}$ are all 1 in the
index $i$ (similar argument as before), so the sum of coefficients is 0 for
each pair, and so for all coefficients corresponding to vectors in $W$.

This finishes the proof of (7), and so $v_{P}$ is a linear combination of the
vectors $u_{T}$. From the result above and Lemma 13 we deduce that $G$ admits
$P$-sparsification with error $\varepsilon$ using
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$ hyperedges, as
required. ∎

To complete the picture for even $k$, we reduce to Proposition 14 by a simple
“complementarity trick”

######  Proposition 15.

Let $k$ be an even number, and $G$ a $k$-uniform hypergraph. Let $P$ be a
$k$-ary Boolean predicate. Then for every $\varepsilon>0$, $G$ admits
$P$-sparsification with error $\varepsilon$ using
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$ hyperedges.

###### Proof.

If $P(1,1,\ldots,1)=0$ then we are done by Proposition 14. Otherwise, we have
$P(1,1,\ldots,1)=1$, and consider $\overline{P}:\\{0,1\\}^{k}\to\\{0,1\\}$
defined by $\overline{P}(b_{1},\ldots,b_{k})=1-P(b_{1},\ldots,b_{k})$, so
$v_{\overline{P}}$ is the negation of $v_{P}$. Since $\overline{P}$ has
$\overline{P}(1,1,\ldots,1)=0$, Proposition 14 applies, and gives us a
subhypergraph $G_{\varepsilon}$ for each $\varepsilon>0$, such that for every
assignment $a:V\to\\{0,1\\}$ we have

$\left|\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},\overline{P}}(a)-\text{Val}_{G,\overline{P}}(a)\right|\leq\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})).$
(8)

Now, since $v_{P}+v_{\overline{P}}=\textbf{1}$ we have

$\text{Val}_{G,P}(a)+\text{Val}_{G,\overline{P}}(a)=\langle
v_{P},v_{G,a}\rangle+\langle
v_{\overline{P}},v_{G,a}\rangle=\langle\textbf{1},v_{G,a}\rangle=|E|,$

and the same is true for $G_{\varepsilon}$, and so we get

$\text{Val}_{G,\overline{P}}(a)=|E|-\text{Val}_{G,P}(a)$ (9)

and

$\text{Val}_{G_{\varepsilon},\overline{P}}(a)=|E_{\varepsilon}|-\text{Val}_{G_{\varepsilon},P}(a).$
(10)

Using (9) and (10) in (8), we get

$\left|\frac{|E|}{|E_{\varepsilon}|}(|E_{\varepsilon}|-\text{Val}_{G_{\varepsilon},P}(a))-(|E|-\text{Val}_{G,P}(a))\right|\leq\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})),$

and after rearranging,

$\left|\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},P}(a)-\text{Val}_{G,P}(a)\right|\leq\varepsilon(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})),$

as required. ∎

The final piece in the jigsaw shows how to reduce sparsification of
$k$-uniform hypergraphs with $k$ odd to the case of $(k+1)$-uniform
hypergraphs by adding a universal vertex and extending the original predicate
by one dimension.

######  Proposition 16.

Let $k$ be an odd number, and $G=(V,E)$ a $k$-uniform hypergraph. Let $P$ be a
$k$-ary Boolean predicate. Then for every $\varepsilon>0$, $G$ admits
$P$-sparsification with error $\varepsilon$ using
$O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$ hyperedges.

###### Proof.

Let $\varepsilon>0$ and denote $\varepsilon_{0}=\varepsilon\frac{k}{k+1}$.
Consider the hypergraph $G^{\prime}=(V^{\prime},E^{\prime})$ defined by

$V^{\prime}=V\cup\\{v_{0}\\}\quad,\quad
E^{\prime}=\\{(v_{1},\ldots,v_{k},v_{0}):(v_{1},\ldots,v_{k})\in E\\},$

where $v_{0}\notin V$ is a new vertex. Clearly $G^{\prime}$ is a
$(k+1)$-uniform hypergraph, and $k+1$ is even. We define a new predicate
$P^{\prime}:\\{0,1\\}^{k+1}\to\\{0,1\\}$ by

$P^{\prime}(b_{1},\ldots,b_{k+1})=\left\\{\begin{array}[]{lr}1&\qquad
P(b_{1},\ldots,b_{k})=1,b_{k+1}=1\\\
0&\qquad\text{otherwise}\end{array}\right..$

We may therefore apply Proposition 15 for
$G^{\prime},P^{\prime},\varepsilon_{0}$ and deduce that for every assignment
$a^{\prime}:V^{\prime}\to\\{0,1\\}$ we have

$\left|\text{Val}_{G^{\prime}_{\varepsilon_{0}},P^{\prime}}(a^{\prime})-\text{Val}_{G^{\prime},P^{\prime}}(a^{\prime})\right|\leq\varepsilon_{0}(d_{G^{\prime}}|\text{Z}_{a^{\prime}}|+\text{vol}_{G^{\prime}}(\text{Z}_{a^{\prime}}))$
(11)

for some subhypergraph
$G^{\prime}_{\varepsilon_{0}}=(V^{\prime},E^{\prime}_{\varepsilon_{0}}\subseteq
E^{\prime})$ which does not depend on $a^{\prime}$, and which satisfies
$|E^{\prime}_{\varepsilon_{0}}|=O\left(n\varepsilon_{0}^{-2}\log\frac{1}{\varepsilon_{0}}\right)=O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$.

Let $G_{\varepsilon_{0}}=(V,E_{\varepsilon_{0}}\subseteq E)$ be the
corresponding subhypergraph of $G$ (so
$|E_{\varepsilon_{0}}|=O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$),
and for every assignment $a:V\to\\{0,1\\}$ define

$a^{\prime}:V^{\prime}\to\\{0,1\\}\quad,\quad
a^{\prime}(v)=\left\\{\begin{array}[]{lr}a(v)&\qquad v\in V\\\ 1&\qquad
v=v_{0}\\\ \end{array}\right..$

Since the hyperedge $e=(v_{1},\ldots,v_{k})\in E$ is counted in
$\text{Val}_{G,P}(a)$ if and only if the hyperedge
$e^{\prime}=(v_{1},\ldots,v_{r},v_{0})\in E^{\prime}$ is counted in
$\text{Val}_{G^{\prime},P^{\prime}}(a^{\prime})$, we have that

$\text{Val}_{G,P}(a)=\text{Val}_{G^{\prime},P^{\prime}}(a^{\prime}),$

and the same is true for $G_{\varepsilon_{0}}$ and
$G^{\prime}_{\varepsilon_{0}}$. We get

$\displaystyle\left|\text{Val}_{G_{\varepsilon_{0}},P}(a)-\text{Val}_{G,P}(a)\right|$
$\displaystyle=\left|\text{Val}_{G^{\prime}_{\varepsilon_{0}},P^{\prime}}(a^{\prime})-\text{Val}_{G^{\prime},P^{\prime}}(a^{\prime})\right|$
$\displaystyle\leq\varepsilon_{0}(d_{G^{\prime}}|\text{Z}_{a^{\prime}}|+\text{vol}_{G^{\prime}}(\text{Z}_{a^{\prime}}))$
$\displaystyle=\varepsilon_{0}\left(\frac{(k+1)|E^{\prime}|}{|V^{\prime}|}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})\right)$
$\displaystyle=\varepsilon_{0}\left(\frac{(k+1)|E|}{|V|+1}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})\right)$
$\displaystyle\leq\varepsilon_{0}\frac{k+1}{k}\left(\frac{k|E|}{|V|}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})\right)$
$\displaystyle=\varepsilon\left(d_{G}|\text{Z}_{a}|+\text{vol}_{G}(\text{Z}_{a})\right),$

where the second line is due to (11), the next two lines are by the definition
of $G^{\prime}$ and $a^{\prime}$, the fifth line is by rearranging, and the
last line is by the definition of the average degree of $G$. We get the
required result. ∎

Propositions 15 and 16 complete the proof of Theorem 10.

######  Remark 17.

In the proof of Proposition 14 the hypergraph $G_{\varepsilon}$ was chosen
independently of the predicate $P$. Since Propositions 15 and 16 reduce to
that case, we have in fact shown that for every $\varepsilon>0$, Theorem 10 is
witnessed by the same subhypergraph $G_{\varepsilon}$ for all different
predicates $P$. This will be important in the proof of Theorem 20.

######  Remark 18.

We note that our main result, Theorem 10, extends Theorem 3 in the regime
where $k$ is a constant, which is the main focus of this paper. However,
Theorem 3 also works for non-constant $k$ [7]. If $k$ is not a constant, it
can be seen from the proof of Lemma 13 that the number of hyperedges of the
sparse subhypergraph is multiplied by a factor of $O(m^{2})$ (since $O(m)$ is
the proportion between $\varepsilon$ and $\varepsilon_{0}$ given that the
coefficients $\lambda_{i}$ are constant). In Proposition 14 we have $m=2^{k}$,
and so for $k$ not constant we get an additional factor of $4^{k}$.
Furthermore, in Propositions 8 and 14 we obtain extra factors of $k$, by
considering the $k$-partite $k$-fold cover. While the regime with non-constant
$k$ is interesting for cuts, for arbitrary predicates one needs to be careful
about representation as the natural (explicit) representation of (non-
symmetric) predicates requires exponential space in the arity $k$.

##  4 Sparsification of Non-Boolean Predicates

We now focus on non-Boolean predicates; i.e., predicates of the form
$P:D^{k}\to\\{0,1\\}$ with $|D|>2$. Without loss of generality, we assume
$D=[q]$ for some $q\geq 2$. The most natural way of generalising Theorem 10 to
larger domains appears to be to use the same bound with $\text{Z}_{a}=\\{v\in
V:a(v)=0\\}$. This, however, cannot give the desired sparsification result
(cf. Section 5). Instead we use a different and somewhat weaker kind of
generalisation of the Boolean case, and show that all hypergraphs are still
sparsifiable with respect to all predicates using this definition.

######  Definition 19.

Let $P:D^{k}\to\\{0,1\\}$ be a $k$-ary predicate where $D=[q]$. We say that a
$k$-uniform hypergraph $G=(V,E)$ _admits all-but-one $P$-sparsification_ with
error $\varepsilon$ using $O(f(n,\varepsilon))$ hyperedges if there exists a
subhypergraph $G_{\varepsilon}=(V,E_{\varepsilon}\subseteq E)$ with
$|E_{\varepsilon}|=O(f(n,\varepsilon))$ such that for every assignment $a:V\to
D$ we have

$\left|\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},P}(a)-\text{Val}_{G,P}(a)\right|\leq\varepsilon(d_{G}|M_{a}|+\text{vol}_{G}(N_{a})),$
(12)

where $M_{a}$ is the largest set among the sets $\\{v\in V:a(v)=i\\}$, $N_{a}$
is the set with the largest volume among the sets $\\{v\in V:a(v)=i\\}$ for
$0\leq i\leq q-2$, and $d_{G}$ is the average degree in $G$.

Observe that the maximum in Definition 19 is over $i=0,\ldots,q-2$ without
$i=q-1$, hence the name “all-but-one”. We note that there is nothing special
about $q-1$ and any value from $[q]$ could be chosen in Definition 19.

Under Definition 19, Theorem 10 generalises.

######  Theorem 20.

For every $k$-uniform hypergraph $G=(V,E)$, every $k$-ary predicate
$P:D^{k}\to\\{0,1\\}$ with $D=[q]$ ($k,q$ are constants), and every
$\varepsilon>0$, $G$ admits $P$ all-but-one sparsification with error
$\varepsilon$ using $O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$
hyperedges.

Note that in the case of $q=2$ we have $P:\\{0,1\\}^{k}\to\\{0,1\\}$, and
Definition 19 and Theorem 20 coincide with Definition 9 and Theorem 10. This
is because when $q=2$ the definitions of $M_{a},N_{a}$ coincide with the
definition of $\text{Z}_{a}$ in the Boolean case.

In order to prove Theorem 20, we will generalise our notations from Section 3.
For a $k$-ary predicate $P:D^{k}\to\\{0,1\\}$ we consider the vector
$v_{P}\in\mathbb{R}^{q^{k}}$, defined by $v_{P}[i]=P(\text{rep}_{q,k}(i))$.
For a given hypergraph $G$ and an assignment $a$, we consider the vector
$v_{G,a}\in\mathbb{R}^{q^{k}}$ defined by
$v_{G,a}[i]=\left|\\{(v_{1},\ldots,v_{k})\in
E:(a(v_{1}),\ldots,a(v_{k}))=\text{rep}_{q,k}(i)\\}\right|$. In other words,
each coordinate of $v_{G,a}$ counts the hyperedges in $G$ whose vertices are
assigned some specific set of values by $a$. Under these notations, just as
before, we get $\text{Val}_{G,P}(a)=\langle v_{P},v_{G,a}\rangle$, where
$\langle\cdot,\cdot\rangle$ is the standard inner product in
$\mathbb{R}^{q^{k}}$.

We start by proving the result for _singleton predicates_ , i.e. for
predicates $P$ such that $v_{P}=e_{r}$ for some $0\leq r\leq q^{k}-1$.

######  Lemma 21.

Let $G=(V,E)$ be a $k$-uniform hypergraph, and $P:D^{k}\to\\{0,1\\}$ a $k$-ary
singleton predicate with $D=[q]$ ($k,q$ are constants). For every
$\varepsilon>0$, $G$ admits $P$ all-but-one sparsification with error
$\varepsilon$ using $O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right)$
hyperedges.

###### Proof.

Denote $\varepsilon_{0}=\frac{\varepsilon}{q}$. Let
$\gamma(G)=(V^{\gamma},E^{\gamma})$ be the $k$-partite $k$-fold cover of $G$,
and let
$\gamma(G)_{\varepsilon_{0}}=(V^{\gamma},E_{\varepsilon_{0}}^{\gamma}\subseteq
E^{\gamma})$ be the subhypergraph promised by Theorem 10. From Remark 17 we
know that this is the same subhypergraph for all predicates, and it does not
depend on the choice of $P$. As before, let
$G_{\varepsilon_{0}}=(V,E_{\varepsilon_{0}}\subseteq E)$ be the subhypergraph
of $G$ which satisfies
$\gamma(G_{\varepsilon_{0}})=\gamma(G)_{\varepsilon_{0}}$.

Let $r$ be the integer for which $v_{P}=e_{r}$, and denote
$u_{r}=\text{rep}_{q,k}(r)$. Consider the set $T=\\{i\in[k]:u_{r}[i]=q-1\\}$.
For each assignment $a:V\to[q]$, we want to find a Boolean assignment
$a_{r}:V^{\gamma}\to\\{0,1\\}$ which does not assign 0 to any vertices
$v^{(i)}$ which have $a(v)=q-1$, but which can also be used to show
$P$-sparsification. We define

$a_{r}(v^{(i)})=\left\\{\begin{array}[]{lr}0&\qquad i\notin T\text{ and
}a(v)=u_{r}[i]\\\ 0&\qquad i\in T\text{ and }a(v)\neq q-1\\\
1&\qquad\text{otherwise}\end{array}\right..$

We also define a $k$-ary Boolean predicate $P_{r}:\\{0,1\\}^{k}\to\\{0,1\\}$
to only have a single truth value (a singleton) which is
$(b_{1},\ldots,b_{k})$ where $b_{i}=0$ if $i\not\in T$ and $b_{i}=1$
otherwise.

Observe that

$\text{Val}_{G,P}(a)=\text{Val}_{\gamma(G),P_{r}}(a_{r}),$ (13)

since both count the same hyperedges. The same is true for any hypergraph, and
specifically for $G_{\varepsilon_{0}}$, that is

$\text{Val}_{G_{\varepsilon_{0}},P}(a)=\text{Val}_{\gamma(G_{\varepsilon_{0}}),P_{r}}(a_{r}).$
(14)

Using Theorem 10 for $\gamma(G),P_{r},\varepsilon_{0}$ and $a_{r}$ we get

$\displaystyle\left|\frac{|E|}{|E_{\varepsilon_{0}}|}\text{Val}_{G_{\varepsilon_{0}},P}(a)-\text{Val}_{G,P}(a)\right|$
$\displaystyle=\left|\frac{|E^{\gamma}|}{|E_{\varepsilon_{0}}^{\gamma}|}\text{Val}_{\gamma(G_{\varepsilon_{0}}),P_{r}}(a_{r})-\text{Val}_{\gamma(G),P_{r}}(a_{r})\right|$
$\displaystyle\leq\varepsilon_{0}(d_{\gamma(G)}|\text{Z}_{a_{r}}|+\text{vol}_{\gamma(G)}(\text{Z}_{a_{r}}))$
$\displaystyle\leq\varepsilon_{0}\left(\frac{d_{G}}{k}\cdot
kq|M_{a}|+q\cdot\text{vol}_{G}(N_{a})\right)$
$\displaystyle=\varepsilon\left(d_{G}|M_{a}|+\text{vol}_{G}(N_{a})\right),$

where the first line follows from (13), (14) and Definition 6, the second line
is the application of Theorem 10, the third is again Definition 6 and the
definitions of $a_{r},M_{a},N_{a}$, and the last is the definition of
$\varepsilon_{0}$. This is true for every assignment $a$. In addition we have

$|E_{\varepsilon_{0}}|=O\left(n\varepsilon_{0}^{-2}\log\frac{1}{\varepsilon_{0}}\right)=O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right),$

so $G_{\varepsilon_{0}}$ is the required witness. ∎

The proof of Theorem 20 is now an application of Lemma 21 similar to the proof
of Lemma 13.

###### Proof of Theorem 20.

The vector $v_{P}$ satisfies

$v_{P}=\sum_{r=0}^{q^{k}-1}\lambda_{r}e_{r},$

for some $\lambda_{r}\in\\{0,1\\}$ and $e_{r}$ vectors of the standard basis
of $\mathbb{R}^{q^{k}}$. Therefore, for every assignment $a:V\to D$, we have

$\text{Val}_{G,P}(a)=\langle
v_{P},v_{G,a}\rangle=\sum_{r=0}^{q^{k}-1}\lambda_{r}\langle
e_{r},v_{G,a}\rangle=\sum_{r=0}^{q^{k}-1}\lambda_{r}\text{Val}_{G,P_{r}}(a)$
(15)

where $P_{r}$ is the predicate corresponding to the vector $e_{r}$. Let
$G_{\varepsilon_{0}}=(V,E_{\varepsilon_{0}}\subseteq E)$ be the subhypergraph
of $G$ promised by Lemma 21 for $\varepsilon_{0}=\frac{\varepsilon}{q^{k}}$.
Note that this is the same subhypergraph for all predicates $P_{r}$ (see proof
of the lemma). Equation (15) is true for any other hypergraph as well, and in
particular $G_{\varepsilon_{0}}$. Using Lemma 21 for each $P_{r}$, we get

$\displaystyle\left|\frac{|E|}{|E_{\varepsilon_{0}}|}\text{Val}_{G_{\varepsilon_{0}},P}(a)-\text{Val}_{G,P}(a)\right|$
$\displaystyle=\left|\frac{|E|}{|E_{\varepsilon_{0}}|}\sum_{r=0}^{q^{k}-1}\lambda_{r}\text{Val}_{G_{\varepsilon_{0}},P_{r}}(a)-\sum_{r=0}^{q^{k}-1}\lambda_{r}\text{Val}_{G,P_{r}}(a)\right|$
$\displaystyle\leq\sum_{r=0}^{q^{k}-1}\lambda_{r}\left|\frac{|E|}{|E_{\varepsilon_{0}}|}\text{Val}_{G_{\varepsilon_{0}},P_{r}}(a)-\text{Val}_{G,P_{r}}(a)\right|$
$\displaystyle\leq\sum_{r=0}^{q^{k}-1}\lambda_{r}\varepsilon_{0}(d_{G}|M_{a}|+\text{vol}_{G}(N_{a}))$
$\displaystyle\leq q^{k}\varepsilon_{0}(d_{G}|M_{a}|+\text{vol}_{G}(N_{a}))$
$\displaystyle=\varepsilon(d_{G}|M_{a}|+\text{vol}_{G}(N_{a})),$

where the first line follows from (15) for the different hypergraphs, the
second line from the triangle inequality, the third from Lemma 21, the fourth
is due to $\lambda_{r}\in\\{0,1\\}$ for all $r$, and the last is the
definition of $\varepsilon_{0}$. Again,

$|E_{\varepsilon_{0}}|=O\left(n\varepsilon_{0}^{-2}\log\frac{1}{\varepsilon_{0}}\right)=O\left(n\varepsilon^{-2}\log\frac{1}{\varepsilon}\right),$

so we have found an appropriate subhypergraph of $G$. ∎

######  Remark 22.

Similarly to Remark 18, if $k$ and $q$ are not constant we get an additional
factor of $q^{2k}$.

##  5 Optimality of All-But-One Sparsification

One might wonder if there is a different, perhaps stronger way to define
sparsification for predicates on non-Boolean domains. The following example
shows that all-but-one sparsification is optimal.

For a hypergraph $G=(V,E)$ and a fixed assignment $a:V\to[q]$ denote
$S_{i}=\\{v\in V:a(v)=i\\}$ (so $S_{0}=\text{Z}_{a}$). The definition of all-
but-one sparsification lets us take a bound which depends on the sizes and
volumes of all the sets $S_{i}$ except for $S_{q-1}$. In fact, if we try to
take a bound which depends on fewer of these sets, the definition fails to
generalise even the most basic case of the Cut predicate. To see this, it is
sufficient to consider the graph case, i.e. $k=2$. Let us suppose, without
loss of generality, that our bound does not depend on $S_{q-2},S_{q-1}$.
Consider the predicate $\textsf{Cut}:[q]^{2}\to\\{0,1\\}$ defined by
$\textsf{Cut}(x,y)=1\iff x\neq y$. A simple (but lengthy) argument below shows
that cliques do not have a Cut-sparsifier using such a definition. Therefore,
no definition with a bound which depends on “less” is possible, under the
current assumptions.

Let $G=K_{n}$ be the complete graph with $n$ vertices $v_{1},\ldots,v_{n}$.
Moreover, let $G_{\varepsilon}$ be a subgraph of $G$, and consider the
predicate $\textsf{Cut}:[q]^{2}\to\\{0,1\\}$ defined by
$\textsf{Cut}(x,y)=1\iff x\neq y$.

We consider two cases:

Case (1): All vertices in $G_{\varepsilon}$ have the same degree $d>0$.

We look at the assignment $a:V\to\\{0,1\\}$ defined as $a(v_{1})=a(v_{2})=q-2$
and for all $i>2$, $a(v_{i})=q-1$. If $G_{\varepsilon}$ is a Cut-sparsifier of
$G$ then

$\left|\frac{|E|}{|E_{\varepsilon}|}\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a)-\text{Val}_{G,\textsf{Cut}}(a)\right|\leq\varepsilon(d_{G}|S|+\text{vol}_{G}(S))=0,$

where $S$ is some set which depends only on the empty sets
$S_{0},\ldots,S_{q-3}$. If $v_{1},v_{2}$ are neighbours in $G_{\varepsilon}$
this implies

$\frac{n-1}{d}=\frac{\frac{n(n-1)}{2}}{\frac{nd}{2}}=\frac{|E|}{|E_{\varepsilon}|}=\frac{\text{Val}_{G,\textsf{Cut}}(a)}{\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a)}=\frac{2(n-2)}{2(d-1)}=\frac{n-2}{d-1},$

and if they are not then

$\frac{n-1}{d}=\frac{|E|}{|E_{\varepsilon}|}=\frac{\text{Val}_{G,\textsf{Cut}}(a)}{\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a)}=\frac{2(n-2)}{2d}=\frac{n-2}{d}.$

The second option is a contradiction, and the first option implies $d=n-1$,
which means $|E_{\varepsilon}|=|E|$, so $G_{\varepsilon}$ is not a sparsifier.

Case (2): There exist two vertices $v_{i},v_{j}$ with degrees $d_{i}\neq
d_{j}$ in $G_{\varepsilon}$.

We look at two assignments $a_{1}:V\to\\{0,1\\}$ defined by $a_{1}(v_{i})=q-2$
and $a_{1}(v)=q-1$ for $v\neq v_{i}$, and $a_{2}:V\to\\{0,1\\}$ defined by
$a_{2}(v_{j})=q-2$ and $a_{2}(v)=q-1$ for $v\neq v_{j}$. Since

$\frac{\text{Val}_{G,\textsf{Cut}}(a_{1})}{\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a_{1})}=\frac{n-1}{d_{i}}\neq\frac{n-1}{d_{j}}=\frac{\text{Val}_{G,\textsf{Cut}}(a_{2})}{\text{Val}_{G_{\varepsilon},\textsf{Cut}}(a_{2})},$

at least one side of the inequality is different from
$\frac{|E|}{|E_{\varepsilon}|}$. Suppose without loss of generality this is
the left hand side. Then

$\left|\frac{|E|}{|E_{\varepsilon}|}Val_{G_{\varepsilon},\textsf{Cut}}(a_{1})-Val_{G,\textsf{Cut}}(a_{1})\right|>0=\varepsilon(d_{G}|S|+\text{vol}_{G}(S)),$

where again $S$ is some set not depending on $S_{q-2},S_{q-1}$, and so
$G_{\varepsilon}$ is not a Cut-sparsifier of $G$.

Note that the same argument works for any predicate $P$ with
$P(q-2,q-1)=P(q-1,q-2)=1$ and $P(q-2,q-2)=P(q-1,q-1)=0$. Thus if a definition
does not depend on more than just $S_{q-2},S_{q-1}$, it specifically does not
depend on these two, so the same argument still works.

## References

  * [1] Kook Jin Ahn and Sudipto Guha.  Graph sparsification in the semi-streaming model.  In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP’09), Part II, volume 5556 of Lecture Notes in Computer Science, pages 328–338. Springer, 2009.  doi:10.1007/978-3-642-02930-1\\_27.
  * [2] Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani.  Fast estimation of diameter and shortest paths (without matrix multiplication).  SIAM J. Comput., 28(4):1167–1181, 1999.  doi:10.1137/S0097539796303421.
  * [3] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares.  On sparse spanners of weighted graphs.  Discrete & Computational Geometry, 9(1):81–100, 1993.  doi:10.1007/BF02189308.
  * [4] Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang.  On sketching quadratic forms.  In Proceedings of the 7th ACM Conference on Innovations in Theoretical Computer Science (ITCS’16), pages 311––319. ACM, 2016.  doi:10.1145/2840728.2840753.
  * [5] Baruch Awerbuch.  Complexity of network synchronization.  J. ACM, 32(4):804–823, 1985.  doi:10.1145/4221.4227.
  * [6] Baruch Awerbuch, Yossi Azar, Avrim Blum, and Santosh S. Vempala.  New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen.  SIAM J. Comput., 28(1):254–262, 1998.  doi:10.1137/S009753979528826X.
  * [7] Nikhil Bansal, Ola Svensson, and Luca Trevisan.  New notions and constructions of sparsification for graphs and hypergraphs.  Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS’19), pages 910–928, 2019.  doi:10.1109/FOCS.2019.00059.
  * [8] Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie.  New constructions of (alpha, beta)-spanners and purely additive spanners.  In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05), pages 672–681. SIAM, 2005.  URL: http://dl.acm.org/citation.cfm?id=1070432.1070526.
  * [9] Surender Baswana and Sandeep Sen.  A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs.  Random Struct. Algorithms, 30(4):532–563, 2007.  doi:10.1002/rsa.20130.
  * [10] Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava.  Twice-Ramanujan sparsifiers.  SIAM Review, 56(2):315–334, 2014.  doi:10.1137/130949117.
  * [11] András A. Benczúr and David R. Karger.  Approximating s-t Minimum Cuts in $\tilde{O}(n^{2})$ Time.  In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC’96), pages 47–55. ACM, 1996.  doi:10.1145/237814.237827.
  * [12] Béla Bollobás, Don Coppersmith, and Michael Elkin.  Sparse distance preservers and additive spanners.  SIAM J. Discret. Math., 19(4):1029–1055, 2005.  doi:10.1137/S0895480103431046.
  * [13] Richard A. Brualdi, Frank Harary, and Zevi Miller.  Bigraphs versus digraphs via matrices.  Journal of Graph Theory, 4(1):51–73, 1980.  doi:10.1002/jgt.3190040107.
  * [14] Silvia Butti and Stanislav Živný.  Sparsification of binary CSPs.  SIAM J. Discret. Math., 34(1):825–842, 2020.  doi:10.1137/19M1242446.
  * [15] Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Yunbum Kook, Yang P Liu, Richard Peng, Mark Sellke, and Daniel Vaz.  Vertex sparsification for edge connectivity.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’21), 2021.  URL: https://arxiv.org/abs/2007.07862.
  * [16] Shiri Chechik.  New additive spanners.  In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA’13), pages 498–512. SIAM, 2013.  doi:10.1137/1.9781611973105.36.
  * [17] Edith Cohen.  Fast algorithms for constructing t-spanners and paths with stretch t.  SIAM J. Comput., 28(1):210–236, 1998.  doi:10.1137/S0097539794261295.
  * [18] Dorit Dor, Shay Halperin, and Uri Zwick.  All-pairs almost shortest paths.  SIAM J. Comput., 29(5):1740–1759, 2000.  doi:10.1137/S0097539797327908.
  * [19] Michael Elkin and Ofer Neiman.  Near-additive spanners and near-exact hopsets, A unified view.  Bull. EATCS, 130, 2020.  URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/608/624.
  * [20] Arnold Filtser and Robert Krauthgamer.  Sparsification of two-variable valued constraint satisfaction problems.  SIAM J. Discret. Math., 31(2):1263–1276, 2017.  doi:10.1137/15M1046186.
  * [21] Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi.  A general framework for graph sparsification.  SIAM J. Comput., 48(4):1196–1223, 2019.  doi:10.1137/16M1091666.
  * [22] Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde.  Characterizing multiterminal flow networks and computing flows in networks of small treewidth.  J. Comput. Syst. Sci., 57(3):366–375, 1998.  doi:10.1006/jcss.1998.1592.
  * [23] Dmitry Kogan and Robert Krauthgamer.  Sketching cuts in graphs and hypergraphs.  In Proceedings of the 6th ACM Conference on Innovations in Theoretical Computer Science (ITCS’15), pages 367–376. ACM, 2015.  doi:10.1145/2688073.2688093.
  * [24] Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman.  Sparsified cholesky and multigrid solvers for connection laplacians.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC’16), pages 842–850. ACM, 2016.  doi:10.1145/2897518.2897640.
  * [25] Frank Thomson Leighton and Ankur Moitra.  Extensions and limits to vertex sparsification.  In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’2010), pages 47–56. ACM, 2010.  doi:10.1145/1806689.1806698.
  * [26] Ankur Moitra.  Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size.  In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS’09), pages 3–12. IEEE Computer Society, 2009.  doi:10.1109/FOCS.2009.28.
  * [27] Ilan Newman and Yuri Rabinovich.  On multiplicative lambda-approximations and some geometric applications.  SIAM J. Comput., 42(3):855–883, 2013.  doi:10.1137/100801809.
  * [28] David Peleg and Alejandro A Schäffer.  Graph spanners.  Journal of graph theory, 13(1):99–116, 1989.  doi:10.1002/jgt.3190130114.
  * [29] Eden Pelleg and Stanislav Živný.  Additive Sparsification of CSPs.  In Proceedings of the 29th Annual European Symposium on Algorithms (ESA’21), volume 204. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021.
  * [30] Liam Roditty, Mikkel Thorup, and Uri Zwick.  Deterministic constructions of approximate distance oracles and spanners.  In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP’05), volume 3580 of Lecture Notes in Computer Science, pages 261–272. Springer, 2005.  doi:10.1007/11523468\\_22.
  * [31] Tasuku Soma and Yuichi Yoshida.  Spectral sparsification of hypergraphs.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’19), pages 2570–2581, 2019.  doi:10.1137/1.9781611975482.159.
  * [32] Daniel A. Spielman and Nikhil Srivastava.  Graph sparsification by effective resistances.  SIAM J. Comput., 40(6):1913–1926, 2011.  doi:10.1137/080734029.
  * [33] Daniel A. Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC’04), pages 81–90. ACM, 2004.  doi:10.1145/1007352.1007372.
  * [34] Daniel A. Spielman and Shang-Hua Teng.  Spectral sparsification of graphs.  SIAM J. Comput., 40(4):981–1025, 2011.  doi:10.1137/08074489X.
  * [35] David P. Woodruff.  Additive spanners in nearly quadratic time.  In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP’10), volume 6198 of Lecture Notes in Computer Science, pages 463–474. Springer, 2010.  doi:10.1007/978-3-642-14165-2\\_40.