# Approximately counting independent sets in dense bipartite graphs via
subspace enumeration

Charlie Carlson  Department of Computer Science, University of Colorado
Boulder, USA<EMAIL_ADDRESS>,  Ewan Davies  Department of Computer
Science, Colorado State University, Fort Collins, USA<EMAIL_ADDRESS>,  Alexandra Kolla  Department of Computer Science and Engineering, University
of California Santa Cruz, USA<EMAIL_ADDRESS>and  Aditya Potukuchi
Department of Electrical Engineering and Computer Science, York University,
Toronto, Canada<EMAIL_ADDRESS>
###### Abstract.

We give a randomized algorithm that approximates the number of independent
sets in a dense, regular bipartite graph—in the language of approximate
counting, we give an FPRAS for #BIS on the class of dense, regular bipartite
graphs. Efficient counting algorithms typically apply to “high-temperature”
problems on bounded-degree graphs, and our contribution is a notable exception
as it applies to dense graphs in a low-temperature setting. Our methods give a
counting-focused complement to the long line of work in combinatorial
optimization showing that CSPs such as Max-Cut and Unique Games are easy on
dense graphs via spectral arguments. The proof exploits the fact that dense,
regular graphs exhibit a kind of small-set expansion (i.e. bounded threshold
rank), which via subspace enumeration lets us enumerate small cuts
efficiently.

##  1\. Introduction

Exactly computing the number $i(G)$ of independent sets in a graph $G$ is
#P-hard, even when restricted to bipartite graphs [41]. In the general case,
approximating $i(G)$ (to within, say, a constant factor) is NP-hard, even when
restricted to $d$-regular graphs with $d\geq 6$ [20, 45, 46]. Restricted to
_bipartite_ graphs the problem of counting independent sets is known as #BIS,
and the prospect of hardness of approximation is less clear because finding a
maximum independent set can be done in polynomial time. Under polynomial-time
approximation-preserving reductions, many natural counting problems are
equivalent to #BIS [17], and the complexity of approximating #BIS has received
a lot of attention. Existing approximation algorithms for #BIS include “high-
temperature” algorithms that work when degrees on one side of the bipartition
are small [38], “low-temperature” algorithms that require additional
assumptions such as expansion [11, 29] or unbalanced degrees [8], and
exponential-time algorithms that are nonetheless faster than algorithms for
the general, non-bipartite case [24]. The description of these methods in
terms of temperature is due to a common generalization in terms of weighted
counting and strong connections to statistical physics, where counting
(weighted) independent sets corresponds to computing the partition function of
the hard-core model.

The idea that Max-CSP optimization problems such as Max-Cut and Unique Games
should be easy to approximate on dense graphs—perhaps because they have good
expansion properties—is well-established [3, 18, 19]. Many of the techniques
that apply to dense or expanding graphs have been generalized in interesting
directions. In particular, spectral methods give good results in both dense
graphs and expanders, and in many cases can be extended to more refined
structural properties such as small-set expansion and threshold rank to great
effect. Most of the prominent approaches to Max-CSPs relevant to this work
fall into three categories: algorithmic regularity lemmas which began with
Frieze and Kannan [19] and were extended to threshold rank by Oveis Gharan and
Trevisan [39]; convex hierarchies and correlation rounding [4, 6, 25]; and the
spectral technique of subspace enumeration due to Kolla and Tulsiani [36, 37].
Prior to these developments were several algorithms demonstrating that
counting problems on dense graphs admit efficient approximation algorithms [1,
16, 33], though these results do not apply to counting independent sets.

An analogous theme in approximate counting is to obtain algorithms on expander
graphs or random graphs [7, 9, 21, 26, 29]. Despite superficial similarity to
the aforementioned work on Max-CSPs in the sense that these works give
algorithms for dense or expanding instances, there is relatively little work
establishing any common underlying phenomenon that makes Max-CSP problems and
counting problems easy on dense or expanding graphs. A notable exception is
due to Risteski [42], who connected the work on correlation rounding and
convex hierarchies [6] to the broad and well-studied problem of approximating
partition functions. His approach is also known as the variational method.
Regularity methods and correlation rounding do provide some evidence of
structure common to these problems; for example, Coja–Oghlan and various
coauthors have developed a range of regularity lemmas and applied them to both
Max-CSPs and spin models on random graphs [5, 13, 14], and independently
discovered correlation rounding in the context of Gibbs measures and partition
functions [15]. Counting independent sets is not typically one of the examples
studied, though occasionally this is more for convenience than for fundamental
reasons.

In the specific context of #BIS, connections to Max-CSP research are even more
scarce. The polymer approach of Jenssen, Keevash and Perkins [29] is a major
algorithmic breakthrough for #BIS which shows that several prominent #BIS-hard
problems can be approximated in polynomial time on bounded-degree expander
graphs (and thus random $d$-regular graphs for $d=O(1)$). Further refinements
of the method broaden the range of problems covered [21, 26], provide faster
algorithms based on rapid mixing of Markov chains known as polymer dynamics
[11], or weaken the structural properties required by applying container
theorems to combinatorial enumeration problems that arise in the method [9,
32]. None of these developments give polynomial-time algorithms in dense
graphs, however, Carlson, Davies, and Kolla [10] applied the polymer method to
approximate the Potts model partition function on (bounded-degree) graphs with
bounded threshold rank, but the conditions their analysis requires are
prohibitively restrictive, and it is unclear whether their techniques can be
applied to #BIS. While Risteski’s approach has been extended and improved [28,
35], results are stated for spin models with soft constraints such as the
Ising and Potts models, and the approximation guarantees degrade in the
presence of the hard constraints that are inherent to independent sets.

###  1.1. Main result

We specifically address the superficial similarities between algorithms for
Max-CSPs and counting independent sets by giving an algorithm for
approximately counting independent sets in dense, regular bipartite graphs
which combines the highly successful techniques of polymer models, subspace
enumeration, and container theorems for the enumeration of independent sets in
bipartite graphs. Our approximation guarantee is of the strong type typically
sought in approximate counting. We say that a relative
$\varepsilon$-approximation of a real number $x$ is a real number $y$ such
that $e^{-\varepsilon}\leq x/y\leq e^{\varepsilon}$, and a fully polynomial
randomized approximation scheme (FPRAS) is an algorithm that with probability
at least $3/4$ outputs a relative $\varepsilon$-approximation in time
polynomial in the instance size and $1/\varepsilon$.

######  Theorem 1.

For each $\delta\in(0,1)$ there is an FPRAS for #BIS on the class of
$\lfloor\delta n\rfloor$-regular bipartite graphs.

We use spectral methods and subspace enumeration to enumerate small cuts in
$d$-regular bipartite graphs via an $\varepsilon$-net of the vector space
spanned by small eigenvalues of the Laplacian matrix of the graph, influenced
by the use of these methods in combinatorial optimization [2, 36, 37] and
approximate counting. Some of our analysis builds upon the perturbative
approach of [27, 29] and an important refinement of this method due to Jenssen
and Perkins [30] (and with Potukuchi [31]) that uses graph container lemmas of
the type developed by Sapozhenko [43, 44]. While container theorems for
independent sets have been used to control enumeration problems that arise in
establishing the convergence of the cluster expansion [30, 31, 32], and these
have inspired container-like theorems for controlling analogous enumeration
problems [9], our addition of subspace enumeration here has a different
purpose.

In terms of running time, our result improves upon the dense case of an
algorithm of Jenssen, Perkins, and Potukuchi [32] which runs in subexponential
time on $d$-regular bipartite graphs for all $d\geq\omega(1)$. In the case
$d=\Theta(n)$ their algorithm takes time $\exp(\Omega(\log^{4}n))$, and our
contribution works for any accuracy parameter $\varepsilon$, which is not
given by the methods in [32]. The improvement stems from incorporating the
spectral techniques mentioned above, which lets us sidestep algorithmic
cluster expansion. That is, our spectral techniques overcome an obstacle in
the algorithm of [32] related to polynomial accuracy: we can achieve arbitrary
accuracy without resorting to a naive enumeration of polymers (which in this
setting are connected subgraphs of the square of the instance).

An interesting question posed in [32] is whether #BIS admits a general
subexponential-time algorithm. One of our technical contributions is to show
that a perspective on graph spectra involving higher-order eigenvalues and
eigenvectors advances our understanding of #BIS.

##  2\. Overview

Our proof begins with the well-known observation that to enumerate independent
sets in a bipartite graph $G=(X\cup Y,E)$ it suffices to enumerate deviations
from the “ideal” independent set $X$. That is, we have the identity

(1) $i(G)=\sum_{A\subseteq X}2^{|Y\setminus N(A)|},$

because for a fixed $A\subseteq X$, any vertex of $Y\setminus N(A)$ can be
added to $A$ without spanning an edge. An important achievement of [29] is to
give a rigorous proof that in bipartite graphs with strong expansion, typical
independent sets are small deviations from either $X$ or $Y$. An algorithm
follows provided one figures out how to efficiently enumerate the small
deviations and quantify their contributions to $i(G)$; this is done in [29] by
brute force enumeration and cluster expansion. Intuitively, we see a hint of
the main idea in equation (1) as when $G$ is an expander we expect that
$N(A)\gg|A|$ and so the terms on the right-hand side are small unless $|A|$ is
small.

If the bipartite graph is not an expander, then large deviations from $X$ and
$Y$ must be handled. For example, in a $2n$-vertex disjoint union of complete
$d$-regular bipartite graphs, a significant number of independent sets
intersect both $X$ and $Y$ on $\Omega(n)$ vertices. To extend the algorithm to
all bipartite graphs, using an idea from [32] we can separate contributions
from expanding and non-expanding pieces of the deviation $A$. The first step
is to break $A\subseteq X$ in the sum in (1) into pieces with disjoint
neighborhoods. We say that $A$ is _2-linked_ if it is connected in the square
$G^{2}$ of $G$, and note that any $A\subseteq X$ admits a unique partition
into 2-linked subsets that we call _components_. Let $\mathcal{K}(A)$ be the
set of components of $A$. A second refinement step groups the deviations of
2-linked components of $A$ according to their neighborhoods. The _closure_
$[A]$ of a set $A\subseteq X$ is $[A]:=\\{x\in X:N(x)\subseteq A\\}$, and we
say that $A$ is _closed_ if $A=[A]$. Note that $A$ is closed if and only if
each component of $A$ is closed. Then we have

(2) $i(G)=\sum_{\begin{subarray}{c}A\subseteq X\text{ s.t.\ each}\\\
\text{component of $A$ is closed}\end{subarray}}\mathcal{D}_{A}\cdot
2^{|Y\setminus N(A)|},$

where

$\mathcal{D}_{A}:=\prod_{A^{\prime}\in\mathcal{K(A)}}\bigl{|}\\{B\subseteq
A^{\prime}:B~{}\text{is 2-linked and}~{}N(B)=N(A^{\prime})\\}\bigr{|}.$

A subset $A\subseteq X$ is called _$t$ -expanding_ if $|N(A)|=|[A]|+t$, and
(in a slight abuse of terminology that we hope the reader permits)
$t$-contracting if $|N(A)|<|[A]|+t$. For a fixed $t_{0}$ that we determine
later, we split the sum over $A$ according to $t_{0}$-contraction. Then

(3) $i(G)=\sum_{\begin{subarray}{c}A\subseteq X\text{ s.t.\ each}\\\
\text{component of $A$ is closed}\\\ \text{and
$t_{0}$-contracting}\end{subarray}}\mathcal{D}_{A}\cdot 2^{|Y\setminus
N(A)|}\cdot\Xi_{A},$

where $\Xi_{A}$ is defined as follows. For a closed subset $A\subseteq X$, let
$X_{A}=X\setminus N^{2}(A)$ and $Y_{A}=Y\setminus N(A)$. A _polymer_ is a
2-linked subset of $X$, and a tuple of polymers is _compatible_ if their
neighborhoods are pairwise disjoint. Let $\mathcal{P}_{A}$ be the set of
polymers which are subsets of $X_{A}$. Then

$\Xi_{A}:=\sum_{k\geq
0}\sum_{\begin{subarray}{c}\\{B_{1},\dotsc,B_{k}\\}\in\mathcal{P}_{A}\text{
compatible}\\\ \text{s.t.\ each $B_{i}$ not
$t_{0}$-contracting}\end{subarray}}2^{-\sum_{i=1}^{k}|N(B_{i})|},$

where the inner sum is over unordered tuples of compatible polymers, each of
which is not $t_{0}$-contracting (equivalently, $t$-expanding for some $t\geq
t_{0}$). For convenience, we define $\mathcal{A}$ to be the set of all
$A\subseteq X$ with closed, $t_{0}$-contracting components. Then the starting
point for the analysis of our algorithm is the identity

(4) $i(G)=\sum_{A\in\mathcal{A}}\mathcal{D}_{A}\cdot 2^{|Y\setminus
N(A)|}\cdot\Xi_{A},$

derived as above.

Our algorithm simply enumerates the sets $A\in\mathcal{A}$, approximates each
$\mathcal{D}_{A}$ term, and uses the fact (which we must prove) that $1$ is a
good approximation of each $\Xi_{A}$ to approximate $i(G)$. The analysis of
our algorithm thus splits into three separate components. Recall that the
input is a $d$-regular bipartite graph $G$ on $2n$ vertices such that for some
constant $\delta>0$ we have $d=\lfloor\delta n\rfloor$, and an approximation
error $\varepsilon$. We set $t_{0}=C\log(n/\varepsilon)$, where $C=C(\delta)$
is large enough, and the correctness and running time of our algorithm follows
from the results below. Note that for this choice of $t_{0}$ an exponential
such as $4^{t_{0}}$ is polynomial in $n$ and $1/\varepsilon$.

######  Lemma 2.

For $t_{0}\leq 2^{-8}d$, the set $\mathcal{A}=\\{A\subseteq X:A\text{ closed
and $t_{0}$-contracting}\\}$ has size at most $n^{O(1/\delta)}\cdot 4^{t_{0}}$
and can be enumerated in the same time.

The proof of this lemma uses subspace enumeration to find small cuts in $G$,
and then for each such small cut enumerates the sets $A\in\mathcal{A}$ which
are close to the cut. See Section 4.

######  Lemma 3.

Let $A\subseteq X$ be a 2-linked, closed $t_{0}$-contracting set. Then for
$\varepsilon^{\prime},\rho>0$ there is a randomized algorithm running in time
polynomial in $n$, $1/\varepsilon^{\prime}$ and $\log(1/\rho)$ that with
probability at least $1-\rho$ outputs a relative
$\varepsilon^{\prime}$-approximation to the number of 2-linked subsets $B$ of
$A$ such that $N(B)=N(A)$.

This lemma uses straightforward estimation of an expectation by repeated
sampling, and is very similar to the analogous result in [32]. Observe that if
$A\in\mathcal{A}$ has $\ell$ components then running this algorithm on each
component with $\varepsilon^{\prime}\leq\varepsilon/(2\ell)$ yields a relative
$\varepsilon/2$-approximation to $\mathcal{D}_{A}$. We use the upper bound
$\ell\leq 2/\delta=O(1)$ which holds because any $t_{0}$-contracting set must
have size at least $d-t_{0}\geq d/2$ (this inequality requires that
$\varepsilon$ is not exponentially small, but in this case, we can solve the
problem exactly by brute force instead). The proof is in Section 5.

######  Lemma 4.

Let $A\in\mathcal{A}$, then $1\leq\Xi_{A}\leq e^{\varepsilon/2}$.

This result means that $1$ is a relative $\varepsilon/2$-approximation for
each of the $\Xi_{A}$ terms appearing in (4). The proof is based on graph
container methods due to Sapozhenko [43, 44], which have since been refined,
[23], [22] [34], [40], and their application to algorithmic counting [30],
[31], [32]. We give the proof in Section 6.

##  3\. The algorithm and proof of Theorem 1

Input:

A $\lfloor\delta n\rfloor$-regular bipartite graph $G=(X\cup Y,E)$ on $2n$
vertices and an approximation error $\varepsilon>0$.

Output:

A relative $\varepsilon$-approximation $i^{\prime}$ of $i(G)$.

Recall that $C=C(\delta)$ is a large enough constant, and that
$t_{0}=C\log(n/\varepsilon)$. In the following proof, implicit constants in
the $O(\cdot)$ notation are allowed to depend on $\delta$ but not
$\varepsilon$. If $\varepsilon\leq n\exp(-d/(2^{8}C))$ then we can afford to
run a brute force algorithm that computes $i(G)$ exactly in time $e^{O(n)}$
and the running time is still polynomial in $1/\varepsilon$. Otherwise, we
note that for all large enough $n$ we have $d-2^{7}t_{0}\geq d/2$ and run the
following algorithm. For convenience, we assume that $\varepsilon\leq 1$ and
simply run the algorithm for $\varepsilon=1$ if the given $\varepsilon$ is
larger.

First, construct the set $\mathcal{A}$, which can be done in time
$(n/\varepsilon)^{O(1)}$ by Lemma 2. Note also that $|\mathcal{A}|$ is
polynomial in $n$ and $1/\varepsilon$. Then, for each $A\in\mathcal{A}$
compute an approximation $\tilde{\mathcal{D}}_{A}$ of $\mathcal{D}_{A}$ by
running the algorithm of Lemma 3 for each component of $A$ with
$\varepsilon^{\prime}=\varepsilon\delta/4=\Theta(\varepsilon)$ and
$\rho=(n/\varepsilon)^{-C^{\prime}}$ for a large enough constant $C^{\prime}$.
Recall that there are at most $O(1)$ components of each such $A$, and note
that the total number of times the algorithm of Lemma 3 is used is thus
$(n/\varepsilon)^{O(1)}$. By a union bound, with probability at least $3/4$ we
get the desired approximation in each application of the lemma, and thus a
valid relative $\varepsilon/2$-approximation $\tilde{\mathcal{D}}_{A}$ of each
$\mathcal{D}_{A}$. Then output
$i^{\prime}=\sum_{A\in\mathcal{A}}\tilde{\mathcal{D}}_{A}2^{|Y\setminus
N(A)|}$. By Lemma 4 and the analysis above the output is a valid
$\varepsilon$-approximation of $i(G)$ obtained in time
$(n/\varepsilon)^{O(1)}$, thus proving Theorem 1.

##  4\. Subspace enumeration and contracting sets

The proof of Lemma 2 has two parts. First, we show how to enumerate small cuts
using subspace enumeration. For related results see [2, 36, 37]. We use the
term _cut_ to mean a subset of $V=X\cup Y$, and the _value_ $|\nabla(C)|$ of a
cut $C$ is the number of edges with precisely one endpoint in $C$.

######  Lemma 5.

Let $G=(V,E)$ be a $d$-regular bipartite graph on $N=2n$ vertices. There is a
set $\mathcal{C}^{\mathrm{cut}}\subseteq 2^{V}$ such that
$|\mathcal{C}^{\mathrm{cut}}|\leq n^{O(1/\delta)}$ and
$\mathcal{C}^{\mathrm{cut}}$ has the following property. For all $t\geq 1$ and
cuts $S\subseteq V$ with value $|\nabla(S)|\leq td$, there is some
$C\in\mathcal{C}^{\mathrm{cut}}$ such that $|S\mathbin{\triangle}C|\leq 32t$
and $|\nabla(C)|\leq 33td$. Moreover, the set $\mathcal{C}^{\mathrm{cut}}$ can
be constructed in time $n^{O(1/\delta)}$ and hence
$|\mathcal{C}^{\mathrm{cut}}|\leq n^{O(1/\delta)}$.

###### Proof.

Let $d=\lambda_{1}\geq\dotsb\geq\lambda_{N}=-d$ be the spectrum of the
adjacency matrix $A$ of $G$. The facts that $\lambda_{1}=d=\lambda_{N}$ and
that the spectrum of $A$ is symmetric about zero are standard, see e.g. [12].
Let $k$ be such that $A$ has precisely $2k$ eigenvalue of absolute value at
least $d/2$. Counting closed walks of length two gives

$\operatorname{Tr}(A^{2})=Nd=\sum_{i=1}^{N}\lambda_{i}^{2}\geq kd^{2}/2,$

and hence $k\leq 4n/d=O(1/\delta)$.

Let $L=dI-A$ be the Laplacian matrix of $G$ and let
$\mathbf{e}_{1},\dotsc,\mathbf{e}_{N}$ be an orthonormal basis of eigenvectors
of $L$ such that $\mathbf{e}_{i}$ has eigenvalue $\mu_{i}$ with
$0=\mu_{1}\leq\dotsb\leq\mu_{N}=2d$. By the definition of $k$, it must be the
case that $\mu_{k+1}>d/2$. Let $U$ be the span of
$\mathbf{e}_{1},\dotsc\mathbf{e}_{k}$, and $U^{\perp}$ be the orthogonal
complement of $U$. For $\varepsilon=\sqrt{2}$, we require an efficient
construction of an $\varepsilon$-net $\mathcal{E}\subseteq U$ covering all
vectors of $L^{2}$-norm at most $\sqrt{n}$ in $U$ for some $\varepsilon$. For
example, we can take

$\mathcal{E}:=\left\\{\mathbf{p}=\sum_{i=1}^{k}x_{i}\mathbf{e}_{i}:x_{1},\dotsc,x_{k}\in\varepsilon/\sqrt{k}\cdot\mathbb{Z},\,\|\mathbf{p}\|\leq\sqrt{n}\right\\},$

yielding $|\mathcal{E}|\leq(2\sqrt{nk}/\varepsilon)^{k}$. Then every vector in
$U$ with $L^{2}$-norm at most $\sqrt{n}$ lies at most distance $\varepsilon$
from a vector in $\mathcal{E}$.

The algorithm to construct $\mathcal{C}^{\mathrm{cut}}$ is as follows. Start
with $\mathcal{C}^{\mathrm{cut}}=\emptyset$ and for each point
$\mathbf{p}\in\mathcal{E}$, form $\mathbf{p}^{\prime}$ by rounding each
coordinate of $\mathbf{p}$ to $\\{0,1\\}$ (breaking ties with $1/2\mapsto 1$)
and add the vertex subset with indicator vector $\mathbf{p}^{\prime}$ to
$\mathcal{C}^{\mathrm{cut}}$.

We now show that $\mathcal{C}^{\mathrm{cut}}$ has the desired properties. By
the construction of $\mathcal{C}^{\mathrm{cut}}$ and $\mathcal{E}$ we have
$|\mathcal{C}^{\mathrm{cut}}|\leq|\mathcal{E}|\leq n^{O(1/\delta)}$. To
establish the other property of $\mathcal{C}^{\mathrm{cut}}$, let $t\geq 1$
and consider an arbitrary subset $S\subseteq V$ with $|\nabla(S)|\leq td$. Let
$\mathbf{s}$ be the indicator vector of the set $S$ and write this vector in
the eigenbasis of $L$ as $\mathbf{s}=\sum_{i=1}^{N}s_{i}\mathbf{e}_{i}$. Let
$\mathbf{u}=\sum_{i=1}^{k}s_{i}\mathbf{e}_{i}$ be the projection of
$\mathbf{s}$ onto $U$ and let $\mathbf{p}$ be the point in $\mathcal{E}$
closest to $\mathbf{u}$. Indicator vectors of subsets of $V$ have $L^{2}$-norm
at most $\sqrt{n}$, and hence $\|\mathbf{u}-\mathbf{p}\|\leq\varepsilon$.

Without considering our need for an efficient construction, the idea is that
because $\nabla(S)$ is small we know that $\mathbf{s}$ is an indicator vector
close to its projection $\mathbf{u}$ onto $U$. Thus, if we form
$\mathcal{C}^{\mathrm{cut}}$ as the union of all sets whose indicator vectors
are close to vectors in $U$, each set $S$ of interest has an indicator vector
that lies within a distance twice the definition of “close” to a set in $C$.

To make the above sketch efficient, we replace $U$ with the $\varepsilon$-net
$\mathcal{P}$. Note that

$\displaystyle
td\geq|\nabla(S)|=\mathbf{s}^{\mathrm{T}}L\mathbf{s}=\sum_{i=1}^{N}\mu_{i}s_{i}^{2}\geq\frac{d}{2}\sum_{i=k+1}^{N}s_{i}^{2}.$

But $\sum_{i=k+1}^{N}s_{i}^{2}=\|\mathbf{s}-\mathbf{u}\|^{2}$, so we have the
bound $\|\mathbf{s}-\mathbf{u}\|\leq\sqrt{2t}$. Then we immediately have
$\|\mathbf{s}-\mathbf{p}\|\leq\sqrt{2t}+\varepsilon$ from the triangle
inequality. Let $\mathbf{p}^{\prime}$ be obtained from $\mathbf{p}$ by
rounding each coordinate to $\\{0,1\\}$, breaking ties with $1/2\mapsto 1$,
and let $C\subseteq V$ be the set whose indicator vector is
$\mathbf{p}^{\prime}$. We have
$|S\mathbin{\triangle}C|=\|\mathbf{s}-\mathbf{p}^{\prime}\|^{2}$ and we bound
the latter with the triangle inequality. In particular, $\mathbf{s}$ is an
indicator vector of distance at most $\sqrt{2t}+\varepsilon$ from $\mathbf{p}$
and $\mathbf{p}^{\prime}$ must be the closest indicator vector to
$\mathbf{p}$, hence
$\|\mathbf{p}-\mathbf{p}^{\prime}\|\leq\sqrt{2t}+\varepsilon$. Then
$\|\mathbf{s}-\mathbf{p}\|\leq 2(\sqrt{2t}+\varepsilon)$, and because $t\geq
1$ and $\varepsilon=\sqrt{2}$ we have

$|S\mathbin{\triangle}C|\leq 4(\sqrt{t/\delta}+\varepsilon)^{2}\leq 32t.$

It remains to bound the value of the cut $|\nabla(C)|$, and the desired bound
follows from the observation that

$|\nabla(C)|\leq|\nabla(S)|+d|S\mathbin{\triangle}C|\leq td+32td=33td.\qed$

Lemma 5 tells us that there is an efficient construction of a collection
$\mathcal{C}^{\mathrm{cut}}$ of cuts such that any small cut $S$ must be close
to a cut in $\mathcal{C}^{\mathrm{cut}}$ in Hamming distance. We now show that
given a small cut $S$ we can enumerate the sets $A\in\mathcal{A}$ which are
close to $S$. For this to be useful, it must be that each $A\in\mathcal{A}$ is
close to some small cut, and we give the details of this later.

######  Lemma 6.

Fix any $c\geq 1$ and let $t\leq\frac{d}{8c}$. Given a cut $C$ with value at
most $td$, there are at most $4^{t}$ closed $t$-contracting subsets
$A\subseteq X$ such that $|A\mathbin{\triangle}(C\cap X)|\leq ct$ and
$|N(A)\mathbin{\triangle}(C\cap Y)|\leq ct$. Moreover, these sets $A$ can be
enumerated in time $4^{t}\cdot n^{O(1)}$.

###### Proof.

Let $A^{\prime}:=C\cap X$ and $W^{\prime}:=C\cap Y$. By the fact that $G$ is
$d$-regular, $|E(A^{\prime},W^{\prime})|\leq
d\min\\{|A^{\prime}|,|W^{\prime}|\\}$ and hence $|\nabla(C)|\geq
d\max\bigl{\\{}|W^{\prime}|-|A^{\prime}|,|A^{\prime}|-|W^{\prime}|\bigr{\\}}$.
By assumption, we have $|\nabla(C)|\leq td$ and therefore
$\bigl{|}|W^{\prime}|-|A^{\prime}|\bigr{|}\leq t$.

Set

$\displaystyle S_{X}$ $\displaystyle:=\bigl{\\{}v\in X\setminus
A^{\prime}:|N(v)\setminus W^{\prime}|\leq 3ct\bigr{\\}},~{}\text{and}$
$\displaystyle S_{Y}$ $\displaystyle:=\bigl{\\{}v\in W^{\prime}:|N(v)\cap
A^{\prime}|\leq ct\bigr{\\}},$

so that $S_{X}\subseteq X$ consists of vertices in $X\setminus A^{\prime}$
with almost all of their neighbors in $W^{\prime}$ and $S_{Y}\subseteq Y$
consists of vertices in $W^{\prime}$ with almost all of their neighbors in
$X\setminus A^{\prime}$. We have the following claims.

######  Claim 7.

For any closed, $t$-contracting subset $A\subseteq X$ such that
$|A\mathbin{\triangle}A^{\prime}|\leq ct$, $A\setminus A^{\prime}\subseteq
S_{X}$.

###### Proof.

Suppose for contradiction that there is a vertex $v\in A\setminus A^{\prime}$
such that

$|N(v)\setminus W^{\prime}|>3ct.$

We derive the contradiction using the facts that $|\nabla(A\cap
A^{\prime})|=d|A\cap A^{\prime}|$ and that any of the edges in $\nabla(A\cap
A^{\prime})$ not incident to $W^{\prime}$ contribute to the value of the cut
$C$. These facts imply that $|E(A\cap A^{\prime},W^{\prime})|\geq d|A\cap
A^{\prime}|-t\cdot d$, and hence

$|N(A\cap A^{\prime})\cap W^{\prime}|\geq|A\cap A^{\prime}|-t.$

Then because $A$ is closed and non-expanding,

$\displaystyle|A|+t$ $\displaystyle\geq|N(A)|\geq|N((A\cap
A^{\prime})\cup\\{v\\})|$ $\displaystyle>|N((A\cap A^{\prime})\cup\\{v\\})\cap
W^{\prime}|+3ct$ $\displaystyle\geq|A\cap A^{\prime}|+2ct\geq|A|+ct,$

which is a contradiction because there is a strict inequality in the chain and
$c\geq 1$. ∎

######  Claim 8.

For any $t$-contracting subset $A\subseteq X$ such that
$|A\mathbin{\triangle}A^{\prime}|\leq ct$, $W^{\prime}\setminus N(A\cap
A^{\prime})\subseteq S_{Y}$.

###### Proof.

We note that for each vertex $v$ in $W^{\prime}\setminus N(A\cap A^{\prime})$,
we have that

$N(v)\cap A^{\prime}\subseteq A^{\prime}\setminus A.$

Since $|A^{\prime}\setminus A|\leq ct$, it follows that $|N(v)\cap
A^{\prime}|\leq ct$. ∎

We can now complete the proof of the lemma. Using the degree constraints in
the definitions of $S_{X}$ and $S_{Y}$, we have

$\displaystyle td$ $\displaystyle\geq|\nabla(C)|$
$\displaystyle\geq|S_{X}|(d-3ct)+|S_{Y}|(d-ct)$
$\displaystyle\geq(d/2)\cdot(|S_{X}|+|S_{Y}|)$

where the last inequality uses $t<\frac{d}{8c}$. As a result, we have

$|S_{X}|+|S_{Y}|\leq 2t.$

Putting Claim 7 and Claim 8 together, we have that each closed $t$-contracting
sets $A$ with
$|A\mathbin{\triangle}A^{\prime}|,~{}|N(A)\mathbin{\triangle}W^{\prime}|\leq
ct$ must be of the form

$A=[(A^{\prime}\setminus N(S_{Y}^{\prime}))\cup S_{X}^{\prime}]$

for some subsets $S_{Y}^{\prime}\subseteq S_{Y}$ and $S_{X}^{\prime}\subseteq
S_{X}$. Thus, the total number of such $A$ is at most $2^{|S_{X}|+|S_{Y}|}\leq
4^{t}$. Since we are given the cut $C$, $S_{X}$ and $S_{Y}$ can be found in
time polynomial in $n$ as required. ∎

With these ingredients we can proof Lemma 2, which we recall states that
$\mathcal{A}$ can be enumerated in time $n^{O(1/\delta)}4^{t_{0}}$.

###### Proof of Lemma 2.

Since $d=\lfloor\delta n\rfloor$, we construct $\mathcal{C}^{\mathrm{cut}}$ as
in Lemma 5 in time $n^{O(1/\delta)}$. We then choose $c=32$ and enumerate for
each $C\in\mathcal{C}^{\mathrm{cut}}$, every closed $t_{0}$-contracting subset
$A$ with $|A\mathbin{\triangle}(C\cap X)|\leq 32t_{0}$ and
$|N(A)\mathbin{\triangle}(C\cap Y)|\leq 32t_{0}$ using Lemma 6. We are done if
every $A\in\mathcal{A}$ appears in this enumeration process, as the running
times combine to give the required $n^{O(1/\delta)}4^{t_{0}}$. This holds
because each $A\in\mathcal{A}$ is closed and $t_{0}$-contracting and hence
setting $S_{A}=A\cup N(A)$ we have $\nabla(S)\leq t_{0}d$. This is because
$d|A|$ edges lie between $A$ and $N(A)$ and $|N(A)|<t_{0}$. So each
$A\in\mathcal{A}$ corresponds to a cut of value at most $t_{0}d$ and hence
some $C\in\mathcal{C}^{\mathrm{cut}}$ has $|S_{A}\mathbin{\triangle}C|\leq
32t_{0}$ by Lemma 5. ∎

##  5\. Approximating the number of covers

For convenience, we restate Lemma 3 here. See 3

###### Proof.

The method is exactly the same as [32, Lem. 17], but in our setting with
$d=\lfloor\delta n\rfloor$ the resulting algorithm runs in time polynomial in
$n$.

Let $|A|=a$, $N(A)=W$ have size $|W|=w$, and let $W^{\prime}=\\{v\in
W:|N(v)\cap A|\leq d/2\\}$ have size $|W^{\prime}|=w^{\prime}$. Let

$\mathcal{D}=\\{B\subseteq A:N(B)=W~{}\text{and $B$ is 2-linked}\\}$

be the set whose size we wish to estimate.

By [32, Cor. 10], there is a 2-linked subset $A^{\prime}\subseteq A$ of size
at most

$\frac{2a}{d}\log d+\frac{2w}{d}+2(w-a)\leq\frac{2}{\delta}\left(1+\log
n\right)+2t_{0}$

such that $N(A^{\prime})=W$. Then $|\mathcal{D}|\geq
2^{a-\left(\frac{2}{\delta}\left(1+\log n\right)+2t_{0}\right)}$, because any
subset of $A$ which contains $A^{\prime}$ is 2-linked. Now $|\mathcal{D}|$ can
be estimated to relative error $\varepsilon^{\prime}$ with probability at
least $1-\rho$ by sampling

$\frac{1}{(\varepsilon^{\prime})^{2}}\log(1/\rho)n^{O(1/\delta)}4^{t_{0}}$

subsets of $A$ uniformly at random, and this can be proved with a suitable
application of the Chernoff bound. ∎

##  6\. Enumerative lemmas

In this section we prove Lemma 4 which states that for $A\in\mathcal{A}$ we
have $1\leq\Xi_{A}\leq e^{\varepsilon/2}$.

###### Proof of Lemma 4.

For the proof, we fix an arbitrary $A\in\mathcal{A}$. The terms in the sum
giving $\Xi_{A}$ are non-negative, and the lower bound comes from the term
$k=0$ which contributes $1$. For the upper bound, we use recent results on
graph containers and adapt them to our purposes.

Recall that a polymer is a 2-linked subset $B\subseteq X$ and that the
function $\Xi_{A}$ involves a sum over tuples of non-$t_{0}$-contracting
polymers. For convenience, we define $\mathcal{G}(w,t)$ to be the set of
$t$-expanding polymers with neighborhood size $w$,

$\mathcal{G}(w,t)=\\{B\subseteq X,\text{ polymer}:|N(B)|=w,|N(B)|-|[B]|=t\\}.$

In terms of this notation, we have

(5) $\displaystyle\Xi_{A}$ $\displaystyle=\sum_{k\geq
0}\sum_{\begin{subarray}{c}\\{B_{1},\dotsc,B_{k}\\}\in\mathcal{P}_{A}\text{
compatible}\\\ \text{s.t.\ each $B_{i}$ not
$t_{0}$-contracting}\end{subarray}}2^{-\sum_{i=1}^{k}|N(B_{i})|}$ (6)
$\displaystyle\leq\sum_{k\geq 0}\frac{1}{k!}\left(\sum_{t\geq
t_{0}}\sum_{w\geq 0}|\mathcal{G}(w,t)|2^{-w}\right)^{k},$

where we drop the requirement on the tuples of being compatible and relax the
requirement that the $B_{i}$ are subsets of $X_{A}$ to being subsets of $X$,
and hence have an upper bound. To proceed, we require upper bounds on
$|\mathcal{G}(w,t)|$ and split into two cases according to $t$. The following
results are proved in the rest of this section and Appendix A.

######  Lemma 9.

There is an absolute constant $\gamma>0$ such that for $t_{0}\leq
t\leq\log^{4}n$, and any integer $w$,

$|\mathcal{G}(w,t)|\leq 2^{w-\gamma t}.$

######  Lemma 10.

There is an absolute constant $\gamma>0$ such that for $t\geq\log^{4}n$, and
any integer $w$,

$|\mathcal{G}(w,t)|\leq 2^{w-\gamma t}.$

We prove Lemma 9 below with some aspects of the container method that are
somewhat standard deferred to the appendix. The proof of Lemma 10 is a simple
application of a result in [32] which we give now.

###### Proof of Lemma 10.

For each $v\in V$, let us define

$\mathcal{G}^{\prime}(v,w,t)=\\{A\in\mathcal{G}(w,t):v\in A\\}.$

First, we observe that
$\log^{2}d\cdot\frac{t}{d}\leq\log^{2}n\cdot\frac{n}{\delta n}\ll\log^{4}n$.
Lemma 4 in [32] gives us that there is a constant $c$ such that for each $v$,
$\mathcal{G}^{\prime}(v,w,t)\leq 2^{w-ct}$. Thus, we have

$|\mathcal{G}(w,t)|\leq\sum_{v}|\mathcal{G}^{\prime}(v,w,t)|\leq n\cdot
2^{n-ct}\leq 2^{n-ct/2}$

for $n$ large enough. Setting $\gamma=c/2$ completes the proof. ∎

With these lemmas in hand, and because each neighborhood size $w$ that we see
is in $[1,n]$, there is an absolute constant $\gamma>0$ such that

(7) $\displaystyle\Xi_{A}$ $\displaystyle\leq\sum_{k\geq
0}\frac{1}{k!}\left(\sum_{t\geq t_{0}}n2^{-\gamma t}\right)^{k}$ (8)
$\displaystyle=\sum_{k\geq 0}\frac{1}{k!}\left(n\frac{2^{-\gamma
t_{0}}}{1-2^{-\gamma}}\right)^{k}=\exp\left(n\frac{2^{-\gamma
t_{0}}}{1-2^{-\gamma}}\right).$

This at most the required $e^{\varepsilon/2}$ provided that

$t_{0}\geq\frac{1}{\gamma}\log_{2}\left(\frac{2}{1-2^{-\gamma}}\frac{n}{\varepsilon}\right),$

which our choice $t_{0}=C\log(n/\varepsilon)$ satisfies for all large enough
constants $C=C(\delta)$. ∎

The rest of this section is dedicated to the proofs of Lemmas 9 and 10. Note
that $\mathcal{G}(w,t)$ is a collection of subsets of $X$ and we are no longer
fixing some $A\in\mathcal{A}$ and focusing on subsets of $X_{A}$.

Given a vertex $v\in V$ and a subset $S\subseteq V$, we write $d_{S}(v)$ for
the number of neighbors of $v$ in $S$. For a subset $A\subseteq X$, we write
$W=N(A)$ and $W_{s}=\bigl{\\{}y\in W:d_{A}(y)\geq s\bigr{\\}}$. We say that
$F$ is an _essential set_ for $A$ if $W\supseteq F\supseteq W_{d/2}$ and
$N(F)\supseteq[A]$. It may be useful to consider such an $F$ an approximation
for the neighborhood $W=N(A)$. We call a tuple $(S,T)\in 2^{X}\times 2^{Y}$ a
$\gamma^{\prime}$-container for a $t$-contracting subset $A\subseteq X$ with
neighborhood $W=N(A)$ if

  1. (i)

$S\supseteq[A]$ and $W_{d/2}\subseteq T\subseteq W$,

  2. (ii)

$d_{Y\setminus T}(v)\leq\gamma^{\prime}t$ for each $v\in S$, and

  3. (iii)

$d_{S}(v)\leq\gamma^{\prime}t$ for each $v\in Y\setminus T$.

The following two results show the existence of containers and bound the
number of sets for which a given container is a $\gamma^{\prime}$-container.

######  Lemma 11.

For any $\gamma^{\prime}>0$ and any set $F\subseteq Y$, there is a set
$\mathcal{C}^{\mathrm{ind}}\subseteq 2^{X}\times 2^{Y}$ of size at most
$n^{O(1/\gamma^{\prime})}$ such that any $A\subseteq X$ for which $F$ is an
essential set, has a $\gamma^{\prime}$-container in
$\mathcal{C}^{\mathrm{ind}}$.

######  Lemma 12.

There is an absolute constant $\gamma^{\prime\prime}>0$ such that the
following holds:

For any $\gamma^{\prime}>0$ any $w<n$, $t<\log^{4}n$ and tuple
$(S,T)\in\mathcal{C}^{\mathrm{ind}}$, there are at most
$2^{w-\gamma^{\prime\prime}t}$ sets $A\in\mathcal{G}(w,t)$ such that $(S,T)$,
and is a $\gamma^{\prime}$-container for $A$.

Since the proofs of these results are small modifications of existing
container results, e.g. [40], we defer their proofs to Appendix A. We are now
ready to handle the case of small $t$ and prove Lemma 9. We leave the proof of
Lemma 10 to Appendix A.

###### Proof of Lemma 9.

Consider an integer $t\in[t_{0},\log^{4}n]$ and a set $A\in\mathcal{G}(w,t)$.
Define $L:=[A]\cup N(A)$. The cut $L$ has value at most $td$. By Lemma 5,
there is a cut $L^{\prime}\in\mathcal{C}^{\mathrm{cut}}$ such that
$g:=|L\mathbin{\triangle}L^{\prime}|\leq O(t)$. Let
$A^{\prime}:=L^{\prime}\cap X$ and $W^{\prime}:=L^{\prime}\cap Y$.

Consider the set $W^{\prime}_{g}=\\{u\in Y:d_{A^{\prime}}(u)>g\\}$. We have
the following two claims.

######  Claim 13.

$W\supseteq W^{\prime}_{g}\supseteq\\{u\in W:d_{A^{\prime}}(u)\geq d/2\\}$.

###### Proof.

Consider a vertex $u\in W$ such that $d_{A}(u)\geq d/2$. We have

$d_{A^{\prime}}(u)\geq d_{A}(u)-|A\setminus A^{\prime}|\geq
d/2-|L\mathbin{\triangle}L^{\prime}|\geq d/2-g>g,$

and hence $u\in W^{\prime}_{g}$. Moreover, consider a vertex $u\in
W^{\prime}_{g}$. We have

$d_{A}(u)\geq d_{A^{\prime}}(u)-|A^{\prime}\setminus
A|>g-|L\mathbin{\triangle}L^{\prime}|>0,$

and hence $u\in W$. ∎

######  Claim 14.

$A\subseteq N(W^{\prime}_{g})$.

###### Proof.

Suppose otherwise, i.e. there is a vertex $u\in A$ such that for each vertex
$v\in N(u)$ we have $d_{A^{\prime}}(u)\leq g$. For any such $v$, we have

$d_{A}(v)\leq d_{A^{\prime}}(v)+|A\setminus A^{\prime}|\leq
d_{A^{\prime}}(v)+|L\mathbin{\triangle}L^{\prime}|\leq 2g.$

This gives us that

$t\cdot d=|E(W,X\setminus A)|\geq|E(N(u),W\setminus A)|\geq d(d-2g),$

contradicting the assumptions that $d=\lfloor\delta n\rfloor$ and $t$ and $g$
are both $O(\log^{4}n)$. ∎

Claims 13 and 14 show that $W^{\prime}_{g}$ is an essential set for $A$. The
set $A\in\mathcal{G}(w,t)$ may be constructed by

  1. (i)

choosing the appropriate cut $L^{\prime}$ in the set
$\mathcal{C}^{\mathrm{cut}}$ constructed in Lemma 5,

  2. (ii)

constructing the essential subset $W^{\prime}_{g}$ for it as above,

  3. (iii)

using Lemma 11 to obtain a $\gamma^{\prime}$-container of $A$, where
$\gamma^{\prime}$ is the absolute constant of Lemma 12, and finally

  4. (iv)

reconstructing $A$ from the $\gamma^{\prime}$-container with Lemma 12.

There are $n^{O(1/\delta)}$ choices for $L^{\prime}$ in the first step, a
unique construction of $W^{\prime}_{g}$ for the second,
$n^{O(1/\gamma^{\prime})}$ possible containers in the third step, and
$2^{w-\gamma^{\prime\prime}t}$ ways for the final step. In total there are

$2^{w-\gamma^{\prime\prime}t+O(1/\gamma^{\prime}+1/\delta)\log n}\leq
2^{w-\gamma^{\prime\prime}t/2}$

such sets $A\in\mathcal{G}(w,t)$. The last inequality comes from our
assumption that $t\geq t_{0}$ for our choice of
$t_{0}=C(\delta)\log(n/\varepsilon)\geq C\log(n)$ (because wlog
$\varepsilon\leq 1$) satisfying

$t_{0}\geq\Omega\left(\frac{\log
n}{\gamma^{\prime\prime}}\left(\frac{1}{\gamma^{\prime}}+\frac{1}{\delta}\right)\right).\qed$

##  7\. Concluding remarks and future directions

  1. 1.

Naturally, a next goal is to understand the power and limitations of the
methods presented, especially in conjunction with existing cluster expansion
methods. More specifically, we are curious about the following two questions:

     * i.

Can this spectral point of view help with our understanding of independent
sets in a larger class of bipartite graphs?

     * ii.

To what extent do these methods help in reducing the computation needed to
implement algorithmic cluster expansion?

In this context, the problem of approximating the number of independent sets
in _small-set expanders_ feels within striking distance.

  2. 2.

Our next remark concerns Lemma 5. As mentioned before, similar results have
had other applications in optimization and Unique Games [2, 36, 37], though we
take a subtly different viewpoint worth noting: we seek to approximate _all_
cuts in the graph, not just small ones. In any case, we find the lemma
interesting in its own right and conjecture something stronger.

######  Conjecture 15.

Lemma 5 holds with $|\mathcal{C}^{\mathrm{ind}}|\leq 2^{O(1/\delta)}$.

If true, this would be best possible, as evidenced by a disjoint union of
$1/\delta$ components. Setting $t=0$ in this case gives exactly $2^{1/\delta}$
cuts of size $0$.

  3. 3.

Finally, we leave open the problem of making our algorithm deterministic. At
the moment, the only step where randomness is used is Lemma 3.

## References

  * [1] J. D. Annan.  A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs.  Combinatorics, Probability and Computing, 3(3):273–283, 1994.  doi:10.1017/S0963548300001188.
  * [2] S. Arora, B. Barak, and D. Steurer.  Subexponential Algorithms for Unique Games and Related Problems.  Journal of the ACM, 62(5):1–25, 2015.  doi:10.1145/2775105.
  * [3] S. Arora, D. Karger, and M. Karpinski.  Polynomial time approximation schemes for dense instances of NP-hard problems.  In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pages 284–293, New York, NY, USA, 1995\. Association for Computing Machinery.  doi:10.1145/225058.225140.
  * [4] S. Arora, S. A. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. K. Vishnoi.  Unique games on expanding constraint graphs are easy: Extended abstract.  In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pages 21–28, Victoria British Columbia Canada, 2008\. ACM.  doi:10.1145/1374376.1374380.
  * [5] V. Bapst and A. Coja-Oghlan.  Harnessing the Bethe free energy.  Random Structures & Algorithms, 49(4):694–741, 2016.  doi:10.1002/rsa.20692.
  * [6] B. Barak, P. Raghavendra, and D. Steurer.  Rounding Semidefinite Programming Hierarchies via Global Correlation.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 472–481, 2011.  doi:10.1109/FOCS.2011.95.
  * [7] A. Blanca, A. Galanis, L. A. Goldberg, D. Stefankovic, E. Vigoda, and K. Yang.  Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs.  In E. Blais, K. Jansen, J. D. P. Rolim, and D. Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.APPROX-RANDOM.2018.33.
  * [8] S. Cannon and W. Perkins.  Counting independent sets in unbalanced bipartite graphs.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1456–1466, 2020.  doi:10.1137/1.9781611975994.88.
  * [9] C. Carlson, E. Davies, N. Fraiman, A. Kolla, A. Potukuchi, and C. Yap.  Algorithms for the ferromagnetic Potts model on expanders.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 344–355, 2022.  doi:10.1109/FOCS54457.2022.00040.
  * [10] C. Carlson, E. Davies, and A. Kolla.  Efficient algorithms for the Potts model on small-set expanders.  To appear in Chicago Journal of Theoretical Computer Science, Mar. 2020, arXiv:2003.01154.
  * [11] Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda.  Fast algorithms at low temperatures via Markov chains.  Random Structures & Algorithms, 58(2):294–321, 2021.  doi:10.1002/rsa.20968.
  * [12] F. Chung.  Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics.  American Mathematical Society, Dec. 1996.  doi:10.1090/cbms/092.
  * [13] A. Coja-Oghlan, C. Cooper, and A. Frieze.  An Efficient Sparse Regularity Concept.  SIAM Journal on Discrete Mathematics, 23(4):2000–2034, 2010.  doi:10.1137/080730160.
  * [14] A. Coja-Oghlan and W. Perkins.  Belief Propagation on Replica Symmetric Random Factor Graph Models.  In K. Jansen, C. Mathieu, J. D. P. Rolim, and C. Umans, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), volume 60 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:15, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.APPROX-RANDOM.2016.27.
  * [15] A. Coja-Oghlan and W. Perkins.  Bethe States of Random Factor Graphs.  Communications in Mathematical Physics, 366(1):173–201, Feb. 2019\.  doi:10.1007/s00220-019-03387-7.
  * [16] M. Dyer, A. Frieze, and M. Jerrum.  Approximately counting Hamilton cycles in dense graphs.  In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’94, pages 336–343, USA, 1994. Society for Industrial and Applied Mathematics.  url:https://dl.acm.org/doi/abs/10.5555/314464.314557.
  * [17] M. Dyer, L. A. Goldberg, C. Greenhill, and M. Jerrum.  The Relative Complexity of Approximate Counting Problems.  Algorithmica, 38(3):471–500, 2004.  doi:10.1007/s00453-003-1073-y.
  * [18] A. Frieze.  A new rounding procedure for the assignment problem with applications to dense graph arrangement problems.  In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, page 21, USA, 1996. IEEE Computer Society.
  * [19] A. Frieze and R. Kannan.  The regularity lemma and approximation schemes for dense problems.  In Proceedings of 37th Conference on Foundations of Computer Science, pages 12–20, 1996.  doi:10.1109/SFCS.1996.548459.
  * [20] A. Galanis, Q. Ge, D. Štefankovič, E. Vigoda, and L. Yang.  Improved inapproximability results for counting independent sets in the hard-core model.  Random Structures & Algorithms, 45(1):78–110, 2014.  doi:10.1002/rsa.20479.
  * [21] A. Galanis, L. A. Goldberg, and J. Stewart.  Fast Algorithms for General Spin Systems on Bipartite Expanders.  ACM Transactions on Computation Theory, 13(4):25:1–25:18, 2021\.  doi:10.1145/3470865.
  * [22] D. Galvin.  A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube.  Combinatorics, Probability and Computing, 20(1):27–51, 2011.  doi:10.1017/S0963548310000155.
  * [23] D. Galvin and P. Tetali.  Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs.  Random Structures & Algorithms, 28(4):427–443, 2006.  doi:10.1002/rsa.20094.
  * [24] L. A. Goldberg, J. Lapinskas, and D. Richerby.  Faster exponential-time algorithms for approximately counting independent sets.  Theoretical Computer Science, 892:48–84, Nov. 2021.  doi:10.1016/j.tcs.2021.09.009.
  * [25] V. Guruswami and A. K. Sinop.  Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives.  In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 482–491. IEEE Computer Society, 2011.  doi:10.1109/FOCS.2011.36.
  * [26] T. Helmuth, M. Jenssen, and W. Perkins.  Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 59(2):817–848, 2023.  doi:10.1214/22-AIHP1263.
  * [27] T. Helmuth, W. Perkins, and G. Regts.  Algorithmic Pirogov–Sinai theory.  Probability Theory and Related Fields, 2019.  doi:10.1007/s00440-019-00928-y.
  * [28] V. Jain, F. Koehler, and A. Risteski.  Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: A unified perspective.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 1226–1236, Phoenix, AZ, USA, 2019. Association for Computing Machinery.  doi:10.1145/3313276.3316299.
  * [29] M. Jenssen, P. Keevash, and W. Perkins.  Algorithms for #BIS-Hard Problems on Expander Graphs.  SIAM Journal on Computing, 49(4):681–710, 2020.  doi:10.1137/19M1286669.
  * [30] M. Jenssen and W. Perkins.  Independent sets in the hypercube revisited.  Journal of the London Mathematical Society, 102(2):645–669, 2020\.  doi:10.1112/jlms.12331.
  * [31] M. Jenssen, W. Perkins, and A. Potukuchi.  Independent sets of a given size and structure in the hypercube.  Combinatorics, Probability and Computing, 31(4):702–720, July 2022\.  doi:10.1017/S0963548321000559.
  * [32] M. Jenssen, W. Perkins, and A. Potukuchi.  Approximately counting independent sets in bipartite graphs via graph containers.  Random Structures & Algorithms, 63(1):215–241, 2023.  doi:10.1002/rsa.21145.
  * [33] M. Jerrum and A. Sinclair.  Approximating the Permanent.  SIAM Journal on Computing, 18(6):1149–1178, 1989.  doi:10.1137/0218077.
  * [34] J. Kahn and J. Park.  The Number of Maximal Independent Sets in the Hamming Cube.  Combinatorica, 42(6):853–880, Dec. 2022.  doi:10.1007/s00493-021-4729-9.
  * [35] F. Koehler, H. Lee, and A. Risteski.  Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods.  In Proceedings of Thirty Fifth Conference on Learning Theory, pages 4945–4988. PMLR, June 2022.  url:https://proceedings.mlr.press/v178/koehler22a.html.
  * [36] A. Kolla.  Spectral Algorithms for Unique Games.  In 2010 IEEE 25th Annual Conference on Computational Complexity, pages 122–130, Cambridge, MA, USA, June 2010. IEEE.  doi:10.1109/CCC.2010.20.
  * [37] A. Kolla and M. Tulsiani.  Playing random and expanding unique games.  Unpublished, 2007.  url:https://home.cs.colorado.edu/~alko5368/UGspec.pdf.
  * [38] J. Liu and P. Lu.  FPTAS for #BIS with Degree Bounds on One Side.  In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 549–556, New York, NY, USA, June 2015. Association for Computing Machinery.  doi:10.1145/2746539.2746598.
  * [39] S. Oveis Gharan and L. Trevisan.  A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.  Theory of Computing, 11(1):241–256, 2015.  doi:10.4086/toc.2015.v011a009.
  * [40] J. Park.  Note on the Number of Balanced Independent Sets in the Hamming Cube.  The Electronic Journal of Combinatorics, page P2.34, 2022.  doi:10.37236/10471.
  * [41] J. S. Provan and M. O. Ball.  The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected.  SIAM Journal on Computing, 12(4):777–788, 1983.  doi:10.1137/0212053.
  * [42] A. Risteski.  How to calculate partition functions using convex programming hierarchies: Provable bounds for variational methods.  In Conference on Learning Theory, pages 1402–1416. PMLR, 2016\.  url:https://proceedings.mlr.press/v49/risteski16.html.
  * [43] A. A. Sapozhenko.  On the number of connected subsets with given cardinality of the boundary in bipartite graphs.  Metody Diskretnogo Analiza, (45):42–70, 96, 1987.
  * [44] A. A. Sapozhenko.  On the number of independent sets in extenders.  Diskretnaya Matematika, 13(1):56–62, 2001.  doi:10.1515/dma.2001.11.2.155.
  * [45] A. Sly.  Computational Transition at the Uniqueness Threshold.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 287–296, Las Vegas, NV, USA, 2010. IEEE.  doi:10.1109/FOCS.2010.34.
  * [46] A. Sly and N. Sun.  The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 361–369, 2012.  doi:10.1109/FOCS.2012.56.

##  Appendix A Deferred proofs

###  A.1. Proof of Lemma 11

We restate the result for convenience.

See 11

###### Proof.

Let $A\subseteq X$ be a subset for which $F$ is an essential set and let
$W=N(A)$, $t:=|N(A)|-|[A]|$. Consider the following algorithm

  * initialize $T\leftarrow F$

  * while $\exists~{}v\in[A]$ s.t. $d_{W\setminus T}(v)>\gamma^{\prime}t$, pick such a $v$:

    * $T\leftarrow T\cup N(v)$

  * initialize $S\leftarrow\\{v\in X:d_{Y\setminus T}(v)\leq\gamma^{\prime}t\\}$

  * while $\exists~{}v\in Y\setminus W$ s.t. $d_{S}(v)>\gamma^{\prime}t$, pick such a $v$:

    * $S\leftarrow S\setminus N(v)$

  * $T\leftarrow T\cup\\{v\in Y:d_{S}(v)>\gamma^{\prime}t\\}$

  * return $(S,T)$

The lemma follows provided we can show that $(S,T)$ as given by the algorithm
above is a $\gamma^{\prime}$-container for $A$ by establishing properties
(i)–(iii), and provided we can show a good enough bound on the total number of
outputs $(S,T)$ which can occur for a fixed $F$ as $A$ varies.

To prove that the output $(S,T)$ is a $\gamma^{\prime}$-container of $A$, we
first show that $S\supseteq[A]$ and $W_{d/2}\subseteq T\subseteq W$,
establishing (i). Since $F$ is an essential subset for $A$, we initialize
$T\leftarrow F$, and $T$ can then only grow, we have $W_{d/2}\subseteq T$.
Clearly, $T\subseteq W$ at the end of the first while loop. After the second
initialize statement, we have that each vertex $v\in[A]$ satisfies
$d_{W\setminus T}(v)\leq d_{Y\setminus T}(v)\leq\gamma^{\prime}t$. Therefore,
$S\supseteq A$ at the end of this line. This property is maintained during the
second while loop since we only delete $N(v)$ from $S$ for $v\not\in W$. This
also means that in the penultimate line, all vertices added to $T$ are from
$W$. Thus $T\subseteq W$ is also maintained at the end of the algorithm. Next,
we prove (iii). At the beginning of the second loop, every $v\in S$ satisfies
$d_{Y\setminus T}(v)\leq\gamma^{\prime}t$. Since vertices are only removed
from $S$ and added to $T$ after this point, this property is preserved till
the end. Finally, to prove (ii) note that the penultimate line of the
algorithm ensures that every $v\in Y\setminus T$ satisfies
$d_{S}(v)\leq\gamma^{\prime}t$.

To bound the number of possible outputs for a fixed $F$, note that before the
start of the first loop we have $|W\setminus T|\leq O(t)$. Each step in the
first loop of the algorithm removes $\gamma t$ vertices from $W\setminus T$.
Therefore, this loop runs at most $O(1/\gamma^{\prime})$ times. Next, each
step in the second loop removes at least $\gamma^{\prime}t$ vertices from
$S\setminus[A]$. Immediately after the second initialize statement, we have

$dt\geq|E(S\setminus[A],T)|\geq(d-\gamma^{\prime}t)|S\setminus[A]|.$

As a result, $|S\setminus[A]|=O(t)$. So the second loop runs for at most
$1/\gamma^{\prime}$ steps. The output is determined by the set of
$O(1/\gamma^{\prime})$ vertices chosen in both loops, so the number of
possible outputs for the algorithm for a given $F$ is at most
$n^{O(1/\gamma^{\prime})}$. ∎

###  A.2. Proof of Lemma 12

We restate the result for convenience. See 12

We need the following lemma

######  Lemma 16.

Let $(S,T)$ be a $\gamma^{\prime}$-container for a set $A\in\mathcal{G}(w,t)$.
Then $|S|\leq|T|$.

###### Proof.

Let us denote $W=N(A)$. First, we observe that $|E(S,W)|\leq
d|T|+\gamma^{\prime}t|W\setminus T|$ by (iii). We also have that $|E(S,W)|\geq
d|[A]|+|S\setminus[A]|(d-\gamma^{\prime}t)=d|S|-\gamma^{\prime}t|S\setminus[A]|$
by (i) and (ii). Combining these inequalities, we have

(9) $|S|\leq|T|+\frac{\gamma^{\prime}t(|S\setminus[A]|+|W\setminus|T||)}{d}.$

Since $T\supseteq W_{d/2}$, we have that $|W\setminus T|\leq O(t)$ and

$\displaystyle td$ $\displaystyle=|E(W,X\setminus[A])|\geq\sum_{v\in
S\setminus[A]}d_{T}(v)\geq|S\setminus[A]|(d-\gamma^{\prime}t)$

which gives $|S\setminus[A]|=O(t)$. So (9) implies

$|S|\leq|T|+O\left(\frac{\gamma^{\prime}t^{2}}{d}\right).$

Since $t\leq\log^{4}n$, $d=\lfloor\delta n\rfloor$, and $|S|$ and $|T|$ are
both integers, we have that $|S|\leq|T|$. ∎

We finish the proof using the following lemma from [40], whose proof we
reproduce for clarity.

######  Lemma 17 ([40], Lemma 11).

There is an absolute constant $\gamma^{\prime\prime}>0$ such that the
following holds:

For any tuple $(S,T)\in 2^{X}\times 2^{Y}$ such that $|S|\leq|T|$, there are
at most $2^{w-\gamma^{\prime\prime}t}$ sets $A\in\mathcal{G}(w,t)$ such that
$[A]\subseteq S$ and $T\subseteq N(A)$.

To be precise, in [40] the graph in question is the $d$-dimensional hypercube
and additional hypotheses are stated, namely $w-t<n/4$ and $w>d^{4}$. These
play no role in the proof, however, and it extends verbatim to the result
stated above.

###### Proof.

Throughout, we denote $W=N(A)$, and let $\alpha>0$ be a constant that will be
determined later.

If $|S|<w-\alpha t$, then $A$ is among the possible $2^{w-\alpha t}$ subsets
of $S$. Suppose otherwise, that $|S|>w-\alpha t$. Let
$A^{*}\in\mathcal{G}(w,t)$ such that $(S,T)$ is a $\gamma^{\prime}$-container
for $A^{*}$ and let $W^{*}=N(A^{*})$. We have that $[A]$ is completely
determined by $W\setminus W^{*}$ and $W^{*}\setminus W$. Since $W^{*}\setminus
W\subseteq W^{*}\setminus T$, and

$|W^{*}\setminus T|\leq|W^{*}|-|T|=|W|-|T|\leq|W|-|S|\leq\alpha t,$

there are at most $2^{\alpha t}$ choices for $W^{*}\setminus W$. Next, for
each vertex in $W\setminus W^{*}$, we choose a neighbor in $A\setminus
A^{*}\subseteq S\setminus A^{*}$. Observe that $W\setminus W^{*}=N(A\setminus
A^{*})\setminus W^{*}$. Since

$|W\setminus W^{*}|\leq|W\setminus F|=|W|-|F|\leq|W|-|S|\leq\alpha t,$

and

$|S\setminus A^{*}|\leq|S|-|A^{*}|=|S|-|A|\leq|T|-|A|\leq|W|-|A|=t.$

Therefore, the number of choices for $W\setminus W^{*}$ is at most

$\binom{t}{\alpha t}\leq 2^{H(\alpha)t}.$

Once we have $[A]$, there are at most $2^{w-t}$ possibilities for $A$. Thus
the total number of choices is at most

$2^{w-t+t(\alpha+H(\alpha))}.$

Choosing e.g., $\alpha=0.17$ allows one to choose
$\gamma^{\prime\prime}=0.17$. ∎


# First Demonstration of a Combined Light and Charge Pixel Readout on the
Anode Plane of a LArTPC

N. Anfimov  A. Branca  J. Bürgi  L. Calivers  C. Cuesta,  R. Diurba,  P. Dunne
D. A. Dwyer  J. J. Evans  A. C. Ezeribe  A. Gauch  I. Gil-Botella  S.
Greenberg,  D. Guffanti  A. Karcher  I. Kreslo,  J. Kunzmann  N. Lane  S.
Manthey Corchado  N. McConkey,  A. Navrer-Agasson  S. Parsa  G. Ruiz Ferreira
B. Russell  A. Selyunin  S. Söldner-Rembold  A. M. Szelc  A. Tapper  F.
Terranova  C. Tognina  G. V. Stenico  M. Weber  and I. Xiotidis

###### Abstract

The novel SoLAr concept aims to extend sensitivities of liquid-argon neutrino
detectors down to the MeV scale for next-generation detectors. SoLAr plans to
accomplish this with a liquid-argon time projection chamber that employs an
anode plane with dual charge and light readout, which enables precision
matching of light and charge signals for data acquisition and reconstruction
purposes. We present the results of a first demonstration of the SoLAr
detector concept with a small-scale prototype detector integrating a pixel-
based charge readout and silicon photomultipliers on a shared printed circuit
board. We discuss the design of the prototype, and its operation and
performance, highlighting the capability of such a detector design.

##  1 Introduction

The next generation of deep underground detectors, DUNE [1] and Hyper-
Kamiokande [2], will enable a substantial leap in the sensitivity of neutrino
physics experiment through their detectors’ mass and precision. Their baseline
design is optimized for the detection of GeV-scale neutrinos produced by a
particle beam with the goal to measure oscillation parameters with
unprecedented precision [3]. In addition, the large mass and the underground
location of the detectors provide a unique opportunity to expand their
sensitivity to lower energy neutrinos, with energies at the MeV-scale,
originating from natural nuclear processes.

Solar neutrinos provide an avenue for these future detectors to explore,
primarily to detect neutrinos generated from the hep branch [4, 5]. Its
discovery directly impacts the modeling of our Sun and the modeling of stellar
evolution throughout the Universe. The application of liquid-argon detectors
to solar-neutrino physics has been explored previously [6, 7, 8]. Such a
detector was found to need an energy resolution at the MeV-scale of $7\%$ to
measure solar neutrinos [6], to have excellent background rejection
capabilities, and to have reasonably low data rates. These requirements are
essential to successfully discriminate the higher-energy tail of the hep
neutrino spectrum from the dominant 8B neutrino spectrum.

One significant challenge is related to readout and computing. The whole DUNE
Far Detector site needs to collect petabytes of light and charge data per year
to accomplish its calibration and neutrino programs from natural sources [1].
Providing a solution that enables large mass detectors while limiting data
rates would significantly increase the feasibility of low-energy searches in
liquid-argon detectors.

Supernova explosions eject most of their energy in form of neutrinos with
energies similar to those of hep neutrinos. A detector that is able to observe
hep neutrinos is by construction also the most precise experiment to detect
supernova explosions. Combining the data with visible, X-ray, $\gamma$-ray,
and gravitational-wave information will provide a complete picture of the
supernova collapse [9].

The SoLAr collaboration proposes to build multipurpose liquid-argon time
projection chambers (LArTPCs) with several kilotons of active mass to detect
beam neutrinos, supernova neutrinos, solar neutrinos, and to search for hep
neutrinos [10]. The main feature of the SoLAr proposal consists of a pixel-
based dual-readout anode plane combining charge and light readout to increase
energy resolution, improve background rejection, and decrease data storage
requirements.
The pixel-based charge readout accomplishes these goals through native three-
dimensional reconstruction. The proposal builds on the progress of pixel-based
LArTPCs being constructed for the Near Detector site at DUNE [11]. In this
detector, light-readout systems will be mounted either underneath or directly
next to the pixels on the anode plane, providing two-dimensional light
reconstruction to accompany the signals from the neighboring charge pixels.

The development of silicon photomultipliers (SiPMs) sensitive to vacuum
ultraviolet (VUV) light is instrumental to the SoLAr proposal. The combination
with charge readout allows for greater sensitivities in reconstruction through
light and charge signal matching. It opens possibilities in online triggering
by sectorizing the detector and triggering specific pixels only when its
neighboring light detector sees a signal.

We aim to use the design concept to build an $\approx 10$ t liquid-argon
SoLAR-type detector with an active volume of about $1.6\times 2\times 2.6$ m3.
Early planning has found the Boulby Underground Laboratory in the United
Kingdom as a suitable location. The Boulby Laboratory is located in a working
polyhalite and salt mine in the North East of England at a depth of $1.1$ km.
The SoLAr detector concept could also be adapted for the instrumentation of
future Far Detector modules for DUNE [10] as part of the DUNE Phase-II
programme [12, 13].

In this paper, we describe the design of the first SoLAr prototype TPC and
present results from the operation of this prototype at the University of Bern
in October 2022.

##  2 Experimental Setup

###  2.1 Design of the SoLAr prototype Time Projection Chamber

The first SoLAr prototype TPC (Prototype-v1) uses a printed circuit board
(PCB) with a pixelated charge readout system using the LArPix chip [14] and
neighboring Hamamatsu VUV SiPMs. The PCB acts as the anode plane and is placed
within an electric field to measure the ionization charge in the liquid argon.
The liquid argon VUV scintillation light from cosmic-ray muons is measured by
the SiPMs. The dimensions of the TPC are $11.8\times 10.8$ cm2 in the $x$ and
$y$ direction, with a sensitive anode area of $7\times 7$ cm2, and $5$ cm in
the drift direction ($z$). The choice is driven by the cryostat inner volume
geometry, which has a diameter of $14$ cm. This size is sufficient to
demonstrate the SoLAr concept by collecting light and charge from cosmic rays
on the same plane.

The active area of the LArTPC is divided into a grid of $16$ identical cells.
Each cell consists of a VUV SiPM (Hamamatsu S13370-6050CN) and 16 charge-
collection pads, resulting in a total of $256$ pixels (see Figure 1).

Figure 1: (a) Schematic of a single cell within the sensitive area of the
LArTPC. Charge-collecting pixels are located directly next to the pin of each
SiPM; (b) the complete v1 prototype with all 16 cells.

(a) (b)

The cathode is a $1$ cm thick metal plate with smooth golden surface and
rounded corners to prevent discharges to the cryostat walls for potentials up
to $10$ kV. The side panel PCBs on the four walls function as electric field
shaping surfaces with nine metalized bands linked through a resistor chain to
create a homogeneous electric field along the electrons’ drift line from the
cathode to the anode.

Figure 2 shows the interior of the TPC with the cathode plate, side panel
PCBs, and the readout anode plate. The assembled TPC connected to a hanging
fixture is shown in Figure 2. The rounded corner rods extending out of the TPC
volume are mechanical guides for insertion into the cryostat and for adjusting
the position and distances of the TPC from the cryostat’s inner walls.

Figure 2: (left) Interior of the SoLAr-v1 TPC time projection chamber with the
cathode plate, the side panels for $E$-field shaping and the readout anode
plate containing the SiPMs and charge pixels. (right) Fully assembled SoLAr-v1
TPC attached to its support structure. The back side of the anode plate with
the four LArPix chips and the back side of one of the E-field shaping panels
with a resistor chain is also visible.

The VUV SiPMs collect the photons in Geiger mode and transfer the analog light
waveform signal to a cold pre-amplifier stage over a short ($20$ cm) double-
layered flex PCB. The signal is then transferred via a feed-through PCB using
SAMTEC micro-coaxial cables to a variable gain amplification (VGA) unit. The
differential amplified signal at this stage is transferred via a twisted-pair
ribbon cable to an analog-to-digital converter (ADC) unit.

The charge collected on the pixel pads is read out with the help of a LArPix
chip, a cryo-rated ASIC for pixelated liquid-argon TPCs, developed by LBNL
[14]. Four LArPix chips are used to read out the $256$ pixels on the anode
plane. The LArPix chip provides a self-triggering digitization and multiplexed
data transfer to a readout hub in warm, referred to as the PACMAN.

Figure 3: Top and side-view of the anode readout plane three-layer stack:
charge (A) and SiPM readout (B), and pixel elevation (C).

The anode readout plane consists of three layers of PCBs mounted on top of
each other, as shown in Figure 3. The charge collection pads are located on
the innermost layer, which contains cutout holes to accommodate the SiPMs
soldered on the second layer. This configuration ensures that the surfaces of
the ceramic-packaged SiPMs are level with the charge collection pixels. This
alignment minimizes electric field deformations near the edges of the SiPMs
and charge collection pads. The second layer hosts the SiPMs and their readout
traces to the connectors. It also contains a network of traces that transmits
the charge signals to the outermost layer, which hosts the LArPix readout
chips and charge readout connector.

The SiPMs operate at a bias voltage of $56$ V at room temperature and $46$ V
at liquid-argon temperature. The setup is designed to provide floating bias
voltages on the SiPMs, such that the top surface of the SiPMs facing the TPC
interior could be set to a negative floating voltage compared to the ground of
the charge pads. In this way, the potential on the SiPMs surface can shape the
electric fields toward the pixels, potentially increasing the charge
collection efficiency.

###  2.2 Electric field simulation

To understand the impact of design choices on the charge collection, the
electric field in proximity of the anode was evaluated numerically using the
COMSOL package [15]. Figure 4 shows the results for the electric field lines.

Figure 4:  (Top) COMSOL numerical evaluation showing the direction and
magnitude of the electric field on the anode plane ($x,y$). The SiPM surface
potential is set to ground. (Bottom) COMSOL electric field numerical
evaluation showing the field lines in the drift direction $z$.

###  2.3 Cryogenics system

We used a triple-layer cryostat to operate the SoLAr prototype with liquid
argon. A vacuum jacket provides thermal insulation for the two volumes of the
cryostat. The outer volume is used as a cooling jacket with liquid argon
constantly flowing through this layer. The inner volume of the cryostat is
filled with liquid argon once and sealed for the full duration of the run.
Figure 5 shows a schematic of the SoLAr Prototype-v1 in the cryostat.

Figure 5: (a) Section view of the CAD drawing of the cryostat and the SoLAr
prototype. The blue region is indicating the vacuum jacket, the orange region
is the outer volume, and the red region is the inner volume with the prototype
detector inside. (b) The cryostat with open lid, where the access to separate
volumes is visible.

The liquid argon passes through a filling filter with copper getters to remove
traces of oxygen and humidity form the LAr. This small setup is not equipped
with re-circulation capabilities and thus the purity of the LAr will
deteriorate over time, giving us a short window to bring up the system and
take cosmic-ray data.

Figure 6:  (a) Top flange with all the feed-throughs and the suspended SoLAr
Prototype-v1 LArTPC shortly before inserting it into the cryostat. (b)
Experimental setup during cryogenics operation.

The level of liquid argon inside the cryostat is controlled with three
temperature sensors at different heights connected to the slow control system.
The slow control system and each readout system has an individual feed through
on the cryostat to transfer data. The bias voltage for the SiPMs is routed
through a separate feed through in order to allow different schemes of
floating from ground. The pressure in the layers of the cryostat is monitored
with two pressure gauges, mounted on the top flange. The inner volume is kept
at an overpressure of $50$ mbar for the duration of the test. Figure 6 shows
the top flange with the assembled SoLAr Prototype-v1 TPC shortly before
insertion into the cryostat and the experimental setup during cryogenic
operation.

##  3 Results

###  3.1 Prototype Operation

In this section, we describe the results obtained with the light and charge
readout based on data collected during the cryogenics operation at the
University of Bern during October 24–26, 2022. After the cryostat had been
filled with liquid argon and the temperature sensors had been submerged, the
cathode voltage was raised to a potential of $2.5$ kV to provide an electric
field of $500$ V/cm.

The data was collected for both the charge and the light readout continuously
with separate self-triggering data acquisition systems. In order to
synchronize, a pulse per second signal from the Global Positioning System
(GPS) was fed to both systems. In addition, a light trigger signal was sent to
the charge readout PACMAN, which is written into the charge data stream as a
$t_{0}$ marker to identify the start time of an event. This enables correct
association of the charge packets’ drift time.

The charge and light data have universal time stamps associated with the
signals measured on both readout systems. These time stamps are used in
offline data processing to associate the light and charge signals, creating
what we defined as “events”, with each event covering a time span of $200$
$\mu$s. The drift distance of $5$ cm requires $\approx 60$ $\mu$s for an
electron to travel the full drift length. The event window is therefore long
enough so that all the charge that is created through ionization at the time
$t_{0}$ can drift from the cathode to the anode. If two light signals occur in
close proximity, only the earliest light signal is used to mark the start of
an event. This can potentially cause some event mismatching which has to be
taken into account in the analysis.

###  3.2 First cosmic-ray tracks with dual-pixel light and charge readout

In Figure 7, we show two representative events, out of around $70,000$
collected during the October 2022 run. The $x$ and $y$ axes represent the span
of the anode plane, while the $z$ direction indicates the drift distance
between the anode and the cathode. The patterns of charge and light signals on
the pixels clearly indicate a muon track candidate. The $zy$ projection is
obtained by extrapolating the drift distance of the electrons to the anode
plane using the light trigger time $t_{0}$. They provide an unambiguous three-
dimensional hit object. This result represents the first combined detection of
charge and light on a dual-pixel anode plane in a LArTPC, which is a major
milestone for demonstrating the fully three-dimensional charge and light
association of the SoLAr concept for triggering and reconstruction purposes
[10].

Figure 7: Two cosmic-ray events recorded by the prototype shown from the anode
view in the $xy$ plane and as $zy$ view, where $z$ is the drift direction. The
$xy$ views show the total light detected by each SiPM in the larger square
pads and the amount of collected charge on each pixel in the smaller square
pads. The color scale represents relative intensity in ADC units. Its range is
tuned for visual aid.

###  3.3 Charge collection per unit length

We evaluate the amount of charge per unit length ($dQ/dx$) on selected events
using through-going tracks selected by applying linear fits to the charge
data. These tracks are analyzed pixel-by-pixel to measure the total amount of
charge each pixel records from what is likely a minimally ionizing cosmic-ray
muon. Figure 8 shows the distribution of charge per unit length for through-
going tracks over a data-taking period of $10$ minutes for $0$ V floating
scheme. The value of each individual pixel channel is subtracted by the value
of said channel from a previously taken pedestal run to equalize the baseline
of said channels. Because approximately half of the pixels were not
functional, the purpose of this study is to show that calorimetry with the
charge information can be represented by a Landau-Gaussian function. The
measurements are presented in ADC/cm.

Figure 8: Charge deposit per unit length for through going cosmic-ray
particles. The uncertainties on the data points are statistical. Each slice
has a length of $1$ cm.

As expected, the distribution of electrons per unit length follows a Landau-
Gaussian distribution, which is consistent with the result of a fit [16]. The
result suggests that the SoLAr Prototoype-v1 charge readout system can carry
out basic charge-based calorimetry. Further calibration and larger-scale
prototypes are necessary to obtain results comparable to similar pixelated
prototype detectors [17] since the volume of the field shell and the active
detector area for charge collection are small, leading to charge loss.

###  3.4 Light collection as a function of SiPM floating voltages

The setup is designed with the possibility to float the voltage level of the
SiPMs with respect to the ground level on the anode surface and the charge
collection pads. In this scheme, the voltage level of both pins of the SiPMs
is simultaneously shifted by a fixed amount while the SiPM bias, the
difference between potential of the two SiPM pins, is kept at the samel value
of $46$ V.

Figure 9: Average light yield detected per unit length of muon tracks as a
function of the SiPM floating voltage, relative to the average light yield
with no floating voltage applied.

Floating the SiPMs to a negative potential may increase the effective charge
collection of neighboring pads by deforming the electric field lines and thus
diverting the drifting electrons away from the SiPMs surface and to the charge
collection pixels (see Figure 4). We study the amount of collected light as a
function of the floating voltage applied to the SiPMs by comparing the average
number of detected photons per unit length of through-going muon tracks for
different floating voltage levels.

Figure 9 shows the number of photo-electrons collected for each floating level
relative to the mean number of collected photo-electrons without any floating
voltage applied to the SiPMs. As expected, the signal strength as a function
of floating voltages is constant within uncertainties.

##  4 Summary

We propose a new concept of anode to read out a LArTPC, integrating charge and
light sensors to perform native 3D reconstruction of an event, which can
detect neutrino interactions from the MeV to GeV energy scale. In this paper,
we present the first demonstration of such an anode plane using an integrated
dual-pixel readout of light and charge pixels, based on a distributed
arrangement of VUV SiPMs. We discuss the design of a small demonstrator,
referred to as SoLAr Prototype-v1, which was operated in October 2022 at the
University of Bern, and present first results. The detector prototype
collected cosmic-ray muon tracks with unambiguous correlations between the
light and charge information. We also study the charge readout per unit length
to demonstrate that this detector has the potential to perform calorimetric
measurements.

The results from this prototype provide valuable information for the design of
future detectors using the integrated light-charge pixel concept. We are
preparing next prototyping stages to characterize and optimize the capability
of the SoLAr concept for LArTPCs to detect neutrino signals at the MeV-scale.

## Acknowledgements

This document was prepared by the SoLAr collaboration. The project has
received funding from the European Union’s Horizon 2020 Research and
Innovation programme under GA no 101004761, by the Italian Ministry for
Research and University (MUR) under Grant Progetto Dipartimenti di Eccellenza
2023-2027, and by the Swiss National Science Foundation. It has also been
supported by several of the collaborating institutions: CIEMAT; Lawrence
Berkeley National Laboratory; University of Bern; University of Manchester;
University of Milano-Bicocca and INFN Sezione di Milano-Bicocca.

## References

  * [1] DUNE collaboration, B. Abi et al., _Deep Underground Neutrino Experiment (DUNE), Far Detector Technical Design Report, Volume I Introduction to DUNE_ , _JINST_ 15 (2020) T08008, [2002.02967].
  * [2] Hyper-Kamiokande collaboration, K. Abe et al., _Hyper-Kamiokande Design Report_ , 1805.04163.
  * [3] DUNE collaboration, B. Abi et al., _Long-baseline neutrino oscillation physics potential of the DUNE experiment_ , _Eur. Phys. J. C_ 80 (2020) 978, [2006.16043].
  * [4] K. Kubodera and T.-S. Park, _The Solar HEP process_ , _Ann. Rev. Nucl. Part. Sci._ 54 (2004) 19–37, [nucl-th/0402008].
  * [5] SNO collaboration, B. Aharmim et al., _Search for $hep$ solar neutrinos and the diffuse supernova neutrino background using all three phases of the Sudbury Neutrino Observatory_, _Phys. Rev. D_ 102 (2020) 062006, [2007.08018].
  * [6] F. Capozzi, S. W. Li, G. Zhu and J. F. Beacom, _DUNE as the Next-Generation Solar Neutrino Experiment_ , _Phys. Rev. Lett._ 123 (2019) 131803, [1808.08232].
  * [7] I. Gil Botella and A. Rubbia, _Decoupling supernova and neutrino oscillation physics with LAr TPC detectors_ , _JCAP_ 08 (2004) 001, [hep-ph/0404151].
  * [8] G. L. Fogli, E. Lisi, A. Marrone and A. Palazzo, _Solar neutrinos: With a tribute to John. N. Bahcall_ , in _3rd International Workshop on NO-VE: Neutrino Oscillations in Venice: 50 Years after the Neutrino Experimental Discovery_ , pp. 69–80, 5, 2006.  hep-ph/0605186.
  * [9] DUNE collaboration, B. Abi et al., _Supernova neutrino burst detection with the Deep Underground Neutrino Experiment_ , _Eur. Phys. J. C_ 81 (2021) 423, [2008.06647].
  * [10] S. Parsa et al., _SoLAr: Solar Neutrinos in Liquid Argon_ , _Snowmass 2021_ (2022) , [2203.07501].
  * [11] DUNE collaboration, V. Hewes et al., _Deep Underground Neutrino Experiment (DUNE) Near Detector Conceptual Design Report_ , _Instruments_ 5 (2021) 31, [2103.13910].
  * [12] DUNE collaboration, A. Abed Abud et al., _Snowmass Neutrino Frontier: DUNE Physics Summary_ , 2203.06100.
  * [13] DUNE collaboration, _DUNE Phase-II: Scientific Opportunities, Detector Concepts, Technological Solutions_ , 2024.
  * [14] D. A. Dwyer et al., _LArPix: Demonstration of low-power 3D pixelated charge readout for liquid argon time projection chambers_ , _JINST_ 13 (2018) P10007, [1808.02969].
  * [15] COMSOL Multiphysics © v.6.2, COMSOL AB, Stockholm, Sweden. https://www.comsol.com.
  * [16] H. Pernegger and M. Friedl, “ROOT reference guide: Convoluted Landau and Gaussian Fitting Function.” https://root.cern/doc/master/langaus_8C.html.
  * [17] DUNE collaboration, A. Abed Abud et al., _Performance of a modular ton-scale pixel-readout liquid argon time projection chamber_ , 2403.03212.