14

# Hypergraph Unreliability in Quasi-Polynomial Time

Ruoxu Cen Department of Computer Science, Duke University. Email:
<EMAIL_ADDRESS>Jason Li Computer Science Department, Carnegie Mellon
University. Email<EMAIL_ADDRESS>Debmalya Panigrahi Department of Computer
Science, Duke University. Email<EMAIL_ADDRESS>
###### Abstract

The hypergraph unreliability problem asks for the probability that a
hypergraph gets disconnected when every hyperedge fails independently with a
given probability. For graphs, the unreliability problem has been studied over
many decades, and multiple fully polynomial-time approximation schemes are
known starting with the work of Karger (STOC 1995). In contrast, prior to this
work, no non-trivial result was known for hypergraphs (of arbitrary rank).

In this paper, we give quasi-polynomial time approximation schemes for the
hypergraph unreliability problem. For any fixed $\varepsilon\in(0,1)$, we
first give a $(1+\varepsilon)$-approximation algorithm that runs in $m^{O(\log
n)}$ time on an $m$-hyperedge, $n$-vertex hypergraph. Then, we improve the
running time to $m\cdot n^{O(\log^{2}n)}$ with an additional exponentially
small additive term in the approximation.

##  1 Introduction

In the hypergraph unreliability problem, we are given an unweighted hypergraph
$G=(V,E)$ and a failure probability $0<p<1$. The goal is to compute the
probability that the hypergraph disconnects111A hypergraph is said to
disconnect due to the failure of a subset of hyperedges when there is a bi-
partition of the vertices such that every surviving hyperedge is entirely
contained on either side of the bi-partition. Equivalently, the failed
hyperedges must contain all hyperedges in some cut of the hypergraph. when
every hyperedge is independently deleted with probability $p$. The probability
of disconnection is called the unreliability of the hypergraph $G$ and is
denoted $u_{G}(p)$. The hypergraph unreliability problem is a natural
generalization of network unreliability which is identically defined but on
graphs (i.e., hypergraphs of rank222The rank of a hypergraph is the maximum
rank of any hyperedge in it, where the rank of a hyperedge is the number of
vertices in it. 2). The latter is a classical problem in the graph algorithms
literature that was shown to be #P-hard by Valiant [Val79] and its algorithmic
study dates back to at least the 1980s [KLM89, AFW95]. By now, several fully
polynomial-time approximation schemes achieving a
$(1+\varepsilon)$-approximation are known for the network unreliability
problem [Kar99, HS18, Kar16, Kar17, Kar20, CHLP24]. In contrast, to the best
of our knowledge, no non-trivial approximation was known for the unreliability
problem on hypergraphs of arbitrary rank prior to this work.

Reliability problems are at the heart of analyzing the robustness of networks
to random failures. (This can be contrasted with minimum cut problems that
analyze the robustness to worst-case failures.) Since real world networks
often exhibit random failures, there is much practical interest in reliability
algorithms with entire books devoted to the topic [Cha16, Col87]. However,
many basic questions remain unanswered from a theoretical perspective. One
bright spot from a theoretical standpoint is the network unreliability
problem, for which the first FPTAS was given by Karger in STOC 1995 [Kar99].
Since then, many other FPTAS have been discovered with ever-improving running
times [HS18, Kar16, Kar17, Kar20, CHLP24], the current record being a recent
$\widetilde{O}(m+n^{1.5})$-time algorithm (for a fixed $\varepsilon$) due to
Cen et al. [CHLP24]. (Throughout the paper, $m$ and $n$ respectively denote
the number of (hyper)edges and vertices in the (hyper)graph.) At the heart of
these algorithms is the well-known fact that a graph has a polynomial number
of near-minimum cuts – cuts whose value exceeds that of the minimum cut by at
most a constant factor [Kar93]. This polynomial bound extends to hypergraphs
of rank at most $O(\log n)$ [KK15] and as a result, the FPTAS for network
unreliability also apply to such hypergraphs. However, this approach fails for
hypergraphs of arbitrary rank. In general, a hypergraph of rank $r$ can have
as many as $\Omega(m\cdot 2^{r})$ near-minimum cuts (see Kogan and Krauthgamer
[KK15] for an example), which rules out an enumeration of the near-minimum
cuts in polynomial time for hypergraphs of large rank. This presents the main
technical challenge in obtaining an approximation algorithm for hypergraph
unreliability, and the main barrier that we overcome in this paper.

In addition to being a natural and well-studied generalization of graphs in
the combinatorics literature, hypergraphs have also gained prominence in
recent years as a modeling tool for real world networks. While graphs are
traditionally used to model networks with point-to-point connections, more
complex “higher-order” interactions in modern networks are better captured by
hypergraphs as observed by many authors in different domains (see, e.g., the
many examples in the recent survey of higher order networks by Bick et al.
[BGHS23]). Indeed, the use of random hypergraphs as a modeling tool for real
world phenomena has also been observed previously [GZCN09]. Therefore, we
believe that the study of reliability in hypergraphs is a natural tool for
understanding the connectivity properties of such real world networks subject
to random failures. We initiate this line of research in this paper and hope
that this will be further expanded in the future.

###  1.1 Our Results

We give two algorithms for hypergraph unreliability. The first algorithm is
simpler and achieves the following result:

######  Theorem 1.1.

For any fixed $\varepsilon\in(0,1)$, there is a randomized Monte Carlo
algorithm for the hypergraph unreliability problem that runs in $m^{O(\log
n)}$ time on an $m$-hyperedge, $n$-vertex hypergraph and returns an estimator
$X$ that satisfies $X\in(1\pm\varepsilon)u_{G}(p)$ whp.333whp = with high
probability. Throughout the paper, we say that a property holds with high
probability if it fails with probability bounded by an inverse polynomial in
$n$.

The running time of the algorithm in the theorem above (and also that in the
next theorem) is inversely polynomial in the accuracy parameter $\varepsilon$.
For brevity, we assume that $\varepsilon$ is fixed throughout the paper and do
not explicitly state this dependence in our running time bounds.

Note that the number of hyperedges in a hypergraph can be exponential in $n$.
This makes a quasi-polynomial-time hypergraph algorithm that has a running
time of $\mathrm{poly}(m)\cdot n^{\mathrm{poly}\log n}$ qualitatively superior
to one that has a running time of $m^{\mathrm{poly}\log(n)}$. (Contrast this
to graphs where the two bounds are qualitatively equivalent because
$m=O(n^{2})$.) To this end, we give a second (more involved) algorithm that
achieves this sharper bound on the running time incurring a small additive
error in the approximation guarantee.

######  Theorem 1.2.

For any fixed $\varepsilon\in(0,1)$ and any $\delta\in(0,1)$, there is a
randomized Monte Carlo algorithm for the hypergraph unreliability problem that
runs in $m\cdot n^{O(\log n\cdot\log\log(1/\delta))}$ time on an
$m$-hyperedge, $n$-vertex hypergraph and returns an estimator $X$ that
satisfies $X\in(1\pm\varepsilon)u_{G}(p)\pm\delta$ whp.

To interpret this result, set $\delta=\exp(-n)$. Then, we get an algorithm
that runs in $m\cdot n^{O(\log^{2}n)}$ time and returns an estimator $X$ that
satisfies $X\in(1+\varepsilon)u_{G}(p)\pm\exp(-n)$ whp. In other words, we
obtain the sharper running time bound that we were hoping for in exchange for
an exponentially small additive error in the approximation. We may also note
that in general, a simple Monte Carlo simulation of the hypergraph
disconnection event also gives an estimator for $u_{G}(p)$ with an additive
error. But, this additive error would be exponentially larger than the one in
Theorem 1.2; in particular, in order to ensure that
$X\in(1\pm\varepsilon)u_{G}(p)+\exp(-n)$ whp, we would need to run the Monte
Carlo simulation $\exp(n)$ times, thereby giving an exponential time algorithm
as against the quasi-polynomial running time in Theorem 1.2.

###  1.2 Our Techniques

We now give a description of the main technical ideas that are used in our
algorithms. Let us start with a rough (polynomial) approximation to
$u_{G}(p)$. In graphs, this is easy. Let $\lambda$ denote the value of a
minimum cut. Since there is at least 1 and at most $O(n^{2})$ minimum cuts
[DKL76], their collective contribution to $u_{G}(p)$ is between $p^{\lambda}$
and $O(n^{2})\cdot p^{\lambda}$. Now, since the number of cuts of value
$\leq\alpha\lambda$ is at most $n^{O(\alpha)}$ [Kar93], the collective
contribution of all other cuts to $u_{G}(p)$ is also at most $O(n^{2})\cdot
p^{\lambda}$ (for sufficiently small $p$, else we can just use Monte Carlo
sampling). The bound of $O(n^{2})$ on the number of minimum cuts continues to
hold in hypergraphs (see [GKP17, CX18]; this is implicitly shown in [Cun83]).
So, their collective contribution is still between $p^{\lambda}$ and
$O(n^{2})\cdot p^{\lambda}$. But, the number of cuts of value
$\leq\alpha\lambda$ can be exponential in the rank $r$, and therefore
exponential in $n$ for $r=\Omega(n)$ [KK15]. Therefore, a naïve union bound
over these cuts only gives a trivial exponential approximation to $u_{G}(p)$.

Our first technical contribution is to show that somewhat surprisingly, the
upper bound of $O(n^{2})\cdot p^{\lambda}$ on the value of $u_{G}(p)$
continues to hold for hypergraphs of arbitrary rank. As described above, we
can’t simply use a union bound over cuts, but must go deeper into the
interactions between different cuts. To this end, we consider an alternative
view444See [Kar20] for a different use of this alternative view. of the random
failure of hyperedges. For each hyperedge, we generate an independent
exponential variable (at unit rate) and superpose the corresponding Poisson
processes on a single timeline. We contract each hyperedge as it appears on
this timeline; then, the disconnection event corresponds to having $\geq 2$
vertices in the contracted hypergraph at time $\ln(1/p)$. As hyperedges
contract, the vertices (which we call _supervertices_) of the contracted
hypergraph represent a partition of the vertices of the original hypergraph;
we assign leaders to the subsets in this partition in a way that we can argue
that any two vertices survive as leaders till time $\ln(1/p)$ with probability
at most $p^{\lambda}$. This allows us to recover the $O(n^{2})\cdot
p^{\lambda}$ bound on the value of $u_{G}(p)$ by a union bound on all vertex
pairs.

We now use this rough $O(n^{2})$ approximation to $u_{G}(p)$ in designing a
recursive algorithm. We generate a random hypergraph $H$ by contracting
hyperedges in $G$ with probability $1-q$ for some $q>p$. (See [Kar16, Kar17,
Kar20, CHLP24] for the use of random contraction in network unreliability.)
The intuition is that by coupling, these edges will survive if the failure
probability is $p$; hence, contracting them does not affect the disconnection
event. The algorithm now makes a recursive call on $H$ with the conditional
failure probability $p/q$ and obtains an estimator for $u_{H}(p/q)$. But, how
do we bound the variance due to the randomness of $H$? This is where the
$O(n^{2})$-approximation comes in handy – it bounds the range of $u_{H}(p/q)$
to $O(n^{2})\cdot(p/q)^{\lambda}$, thereby giving a bound of $n^{2}\cdot
q^{-\lambda}$ on the (relative) variance of the overall estimator.555The
relative variance of a random variable $X$ is defined as
$\mathrm{Var}[X]/\mathbb{E}^{2}[X]$. Thus, if we select $q$ such that
$q^{-\lambda}=\mathrm{poly}(n)$, then we only need a polynomial number of
random trials.

For this plan to work, we need to we make progress in the recursion, i.e.,
make recursive calls on subgraphs that are smaller by a constant factor.
Unfortunately, we are unable to ensure this in hypergraphs of arbitrarily
large rank. To see this, consider a hypergraph containing $n$ hyperedges of
rank $n-1$, i.e., $\lambda=n-1$. In this case, we have $n^{2}\cdot q^{-n+1}$
trials and the probability of each trial returning the input hypergraph is
$q^{n}$ (if none of the $n$ hyperedges is contracted). So, $\geq 1$ recursive
calls (in expectation) will run on the input hypergraph itself, which defeats
the recursion. However, we show that this is really an extreme scenario and we
can make sufficient progress in all hypergraphs with rank at most $n/2$ – we
call these universally small and the rest existentially large hypergraphs.

We are now left to handle existentially large hypergraphs. This is where the
two algorithms (Theorem 1.1 and Theorem 1.2) differ. The first algorithm
(Theorem 1.1) simply enumerates over all outcomes (survival/failure) of the
large hyperedges, i.e., those of rank $>n/2$. To do this efficiently, it
orders the large hyperedges and creates a new recursive instance based on the
first large hyperedge that is contracted in this order. This generates
$\ell\leq m$ subproblems, where $\ell$ denotes the number of large hyperedges.
In the last subproblem, all the $\ell$ large hyperedges fail (i.e., none of
them is contracted) and we are left with a universally small hypergraph. In
all the other subproblems, at least one large hyperedge is contracted and we
are left with a hypergraph containing at most $n/2$ vertices. So, we make
progress in either case.

The second algorithm (Theorem 1.2) cannot afford to enumerate over all large
hyperedges. Instead, it partitions the set of hyperedges in $G$ into the large
and small hyperedges and creates two hypergraphs, $G_{\mathrm{large}}$ and
$G_{\mathrm{small}}$. Now, for $G$ to be disconnected, both
$G_{\mathrm{small}}$ and $G_{\mathrm{large}}$ must be disconnected (but not
vice-versa!). Recall that earlier, we ran into a problem where our naïve
sampling process could not make progress in terms of reducing the size of the
hypergraph when sampling large hyperedges. This was epitomized by a hypergraph
containing $n$ hyperedges of rank $n-1$ each. But, if we think of this
instance in isolation, then it is actually quite easy to estimate $u_{G}(p)$
in this hypergraph. This is because whenever the hypergraph disconnects, it
does so at a degree cut666A degree cut is a cut that separates one vertex from
the rest of hypergraph. of a vertex. So, there are only $n$ cuts that we need
to enumerate over. In fact, this property is true for the hypergraph
$G_{\mathrm{large}}$ obtained from any hypergraph $G$; since every pair of
large hyperedges share at least one vertex, any disconnected sub-hypergraph
must have an isolated vertex. We exploit this property by writing a DNF
formula for all the degree cuts of $G_{\mathrm{large}}$ (where each variable
denotes survival/failure of a large hyperedge) and use the classical
importance sampling technique of Karp, Luby, and Madras [KLM89] to generate a
sample of $G_{\mathrm{large}}$ conditioned on it being disconnected.

How do we augment this sample in $G_{\mathrm{small}}$? We have two cases. To
understand the distinction, let us informally imagine that the minimum cuts of
$G_{\mathrm{large}}$ and $G_{\mathrm{small}}$ coincide, and they form the
minimum cut of $G$. (Of course, this is not true in general!) The two cases
are defined based on the relative values of the minimum cuts in
$G_{\mathrm{large}}$ and $G_{\mathrm{small}}$. If $G_{\mathrm{large}}$
contributes most of the hyperedges to the mincut (we call this the full
revelation case), then the probability that $G_{\mathrm{small}}$ gets
disconnected is quite high (recall that $u_{G}(p)\geq p^{\lambda}$). In this
case, it suffices to do Monte Carlo sampling in $G_{\mathrm{small}}$ to
augment the sample obtained from $G_{\mathrm{large}}$. The other case is when
$G_{\mathrm{small}}$ contributes a sizeable number of hyperedges to the
minimum cut (we call this the partial revelation case). Note that the extreme
example of this second case is when $G_{\mathrm{large}}$ is empty, i.e., when
the hypergraph is universally small. This suggests generalizing the use of
random contraction from universally small hypergraphs to this case, i.e.,
failing hyperedges at a higher probability of $q>p$ in a recursive step. But,
to synchronize the sample across $G_{\mathrm{large}}$ and
$G_{\mathrm{small}}$, we must use the same value $q$ in $G_{\mathrm{large}}$
as well. Unfortunately, as we observed earlier, the algorithm might not make
progress in terms of the size of the hypergraph in this case. To overcome
this, we introduce a second recursive parameter, that of the value of the
failure probability itself. This second recursive parameter now requires us to
define a new base case when the probability of failure is very small (denote
the threshold by a parameter $\delta$) – this is where we incur the additive
loss of $\delta$ in the approximation. The overall running time is now given
by the fact that each subproblem branches into polynomially many subproblems,
and the depth of the recursion is bounded by $\log n\log\log(1/\delta)$ where
the first term comes from the recursion on size and the second term from that
on the failure probability.

##### Organization.

We give some preliminary definitions and terminology in Section 2. We then
establish Theorem 1.1 in Section 3. Finally, we establish Theorem 1.2 in
Section 4. We give some concluding thoughts in Section 5.

##  2 Preliminaries

##### Hypergraphs.

We start with some basic notations for hypergraphs. A hypergraph $G=(V,E)$
comprises a set of vertices $V$ and set of hyperedges $E$, where each
hyperedge $e\in E$ is a non-empty subset of the vertices, i.e.,
$\emptyset\subset e\subseteq V$. The rank of a hyperedge $e$ is $|e|$; the
rank of a hypergraph $G$, denoted $r_{G}$, is the maximum rank of a hyperedge
in $G$.

For any hypergraph $G=(V,E)$ and subset of hyperedges $F\subseteq E$, denote
$G-F:=(V,E\setminus F)$ to be the hypergraph after deleting the hyperedges in
$F$ from $G$. A _cut_ in a hypergraph is defined as a set of edges $C$ such
that $G-C$ is disconnected. The value of a cut $C$ is the number of hyperedges
in $C$. A _minimum cut_ of a hypergraph is a cut of minimum value. We denote
the value of a minimum cut in a hypergraph $G$ by $\lambda_{G}$. The following
is a known result (follows from Theorem 4 in [CQ21] using the maximum flow
algorithm in [CKL+22]):

######  Theorem 2.1.

The minimum cut of a hypergraph can be computed in
$\left(\sum_{e}|e|\right)^{1+o(1)}$ time.

In this paper, we often make use of hyperedge contractions. Contracting a
hyperedge $e$ in a hypergraph $G$ replaces the vertices in $e$ by a single
vertex to form a new hypergraph denoted $G/e:=(V/e,E/e)$. Note that there is a
natural surjective map $\phi:V\to V/e$ that maps vertices in $e$ to the
contracted supervertex in $V/e$, and maps vertices outside $e$ to themselves.
Each hyperedge $e\in E$ is replaced in $E/e$ by an element-wise mapped set
$\\{u\in e:\phi(u)\\}$. By extension, contracting a set of hyperedges
$F=\\{e_{1},e_{2},\ldots\\}$ is equivalent to contracting all hyperedges in
$F$ in arbitrary order: we write $G/F:=(((G/e_{1})/e_{2})\ldots)/e_{k}$. $H$
is called a contracted hypergraph of $G=(V,E)$ if $H=G/F$ for some $F\subseteq
E$. For distinction between the uncontracted vertices in $G$ and the
contracted vertices in $H$, we usually call the former vertices and the latter
supervertices.

A key operation in our algorithm is uniform random hyperedge contraction. We
use $H\sim G(q)$ for some $q\in(0,1)$ to denote the distribution of a random
contracted hypergraph $H$ obtained from $G$ by contracting each hyperedge
independently with probability $1-q$. The next lemma states that $u_{H}(p/q)$
is an unbiased estimator of $u_{G}(p)$:

######  Lemma 2.2.

Suppose $H\sim G(q)$ and $q\geq p$. Then, $\mathbb{E}[u_{H}(p/q)]=u_{G}(p)$.

###### Proof.

Deleting each hyperedge independently with probability $p$ is equivalent to
first choosing each hyperedge with probability $q\geq p$ and then deleting
each chosen edge with probability $p/q$. $u_{G}(p)$ is the probability that
$G$ disconnects in the former distribution. In the latter distribution, note
that the hyperedges that are not chosen must be connected in the resulting
hypergraph after deletion, so contracting them does not affect the
disconnection event of the resulting hypergraph. Thus,
$\mathbb{E}[u_{H}(p/q)]$ is the probability that $G$ disconnects in the latter
distribution. In conclusion, the two probabilities are equal. ∎

##### Random Variables.

Next, we give some basic facts about random variables that we will use in this
paper. All random variables considered in the paper are non-negative.

The relative variance of a random variable $X$ is

$\eta[X]=\frac{\mathrm{Var}[X]}{(\mathbb{E}[X])^{2}}=\frac{\mathbb{E}[X^{2}]}{(\mathbb{E}[X])^{2}}-1.$

Since we use a biased estimator in Theorem 1.2, we need a non-standard
(capped) version of relative variance. We define it and state its properties
below.

######  Definition 2.3 (Capped relative variance).

The _( $\delta$-)capped relative variance_ of random variable $X$ is

$\eta_{\delta}[X]=\frac{\mathrm{Var}[X]}{\max\\{(\mathbb{E}[X])^{2},\delta^{2}\\}}.$

We state some basic facts about capped relative variance (proofs in Appendix
A). Note that relative variance is a special case of capped relative variance
when $\delta=0$. Therefore, these facts also hold for relative variance as a
special case.

######  Fact 2.4.

The average of $M$ independent samples of $X$ has capped relative variance
$\frac{\eta_{\delta}[X]}{M}$.

######  Fact 2.5.

Suppose $Y$ is an unbiased estimator of $x$, and conditioned on a fixed $Y$,
$Z$ is a biased estimator of $Y$ with bias in $[-\delta,0]$ and capped
relative variance $\eta_{\delta}[Z|Y]\leq h$. Then

$\eta_{\delta}[Z]\leq 4\cdot(\eta[Y]+1)\cdot(h+1).$

In particular, when $\delta=0$ (i.e. for relative variance of unbiased
estimator $Z$), there is a stronger bound

$\eta[Z]\leq(\eta[Y]+1)\cdot(h+1)-1.$

######  Fact 2.6.

Suppose $X$ and $Z$ are independent random variables with expectation in
$(0,1)$, and $\delta\in[0,1]$. Then

$\eta_{\delta}[XZ]\leq\eta_{\delta}[X]\cdot\eta_{\delta}[Z]+\eta_{\delta}[X]+\eta_{\delta}[Z].$

######  Lemma 2.7.

The median-of-average of $\frac{\eta_{\delta}[X]}{\varepsilon^{2}}$
independent samples of $X$ is a $(1\pm\varepsilon,\delta)$-approximation of
$\mathbb{E}[X]$.

The next two facts are for relative variance and proved in Appendix A:

######  Fact 2.8.

If $X$ is a convex combination of independent non-negative random variables
$X_{1},\ldots,X_{k}$, i.e., $X=\sum_{i\leq k}\alpha_{i}X_{i}$ for
$\alpha_{i}\geq 0$ and $\sum_{i\leq k}\alpha_{i}=1$, then
$\eta[X]\leq\max_{i\leq k}\eta[X_{i}]$.

######  Fact 2.9.

If a non-negative random variable $X$ is upper bounded by $M$, then
$\eta[X]\leq\frac{M}{\mathbb{E}[X]}-1$.

##### Exponential distribution.

Recall that the exponential distribution of rate $r$ gives a continuous random
variable $X\geq 0$ satisfying $\Pr[X\geq t]=e^{-rt}$ for all $t\geq 0$. We
state some standard properties of the exponential variables:

######  Fact 2.10 (Moment generating function).

Let $X$ follow exponential distribution of rate $r$. Then for any $t<r$,
$\mathbb{E}[e^{tX}]=1/(1-\frac{t}{r})$.

######  Fact 2.11 (Memoryless property).

Let $X$ follow exponentail distribution. Then for any $s,t\geq 0$,
$\Pr[X>s+t|X>s]=\Pr[X>t]$.

######  Fact 2.12.

Let $X_{1},X_{2},\ldots,X_{k}$ be independent random variables with
exponential distribution of rate $r$, and $X=\min_{i\leq k}\\{X_{i}\\}$. Then,
$X$ follows exponential distribution of rate $kr$. Moreover, $X=X_{i}$ for
every value of $i$ with probability $1/k$.

##### Monte Carlo sampling.

Suppose we want to estimate the probability $p_{D}$ that an event $D$ happens.
(For $u_{G}(p)$, $D$ is the event that the hypergraph disconnects.) The Monte
Carlo sampling algorithm first draws a sample from the underlying space. (For
$u_{G}(p)$, it deletes each hyperedge independently with probability $p$.) The
estimator returns 1 if $D$ happens, and 0 otherwise. The following is a
standard property of this estimator (proof in Appendix A):

######  Lemma 2.13.

Monte Carlo sampling outputs an unbiased estimator of $p_{D}$ with relative
variance at most $\frac{1}{p_{D}}$ and $\delta$-capped relative variance at
most $\min\\{\frac{1}{p_{D}},\frac{1}{\delta}\\}$.

Given Lemma 2.13, we can use Lemma 2.7 to obtain the following:

######  Lemma 2.14.

We can obtain a $(1+\varepsilon)$-approximation of $p_{D}$ whp via
$O\left(\frac{\log n}{\varepsilon^{2}\cdot p_{D}}\right)$ Monte Carlo samples
and a $(1+\varepsilon,\delta)$-approximation whp via $O\left(\frac{\log
n}{\varepsilon^{2}\cdot\delta}\right)$ Monte Carlo samples.

##### DNF probability.

In the _DNF probability_ problem, we are given a DNF formula $F$ with $N$
variables and $M$ clauses and a value $p\in(0,1)$. The goal is to estimate the
probability $u_{F}(p)$ that $F$ is satisfied when each variable is True with
probability $p$ independently. This problem is #P-hard even in the special
case of $p=\frac{1}{2}$ [Val79]. In a seminal work, Karp, Luby and Madras
[KLM89] provided an FPRAS in $\widetilde{O}(NM)$ time.

######  Theorem 2.15 ([KLM89]).

The DNF probability problem can be $(1\pm\varepsilon)$-approximated with
success probability $1-\delta$ in $O(NM\ln(1/\delta)/\varepsilon^{2})$ time.

Our algorithm will need an unbiased estimator for DNF probability. The
estimator in Theorem 2.15 could be biased, but we can get an unbiased
estimator by using its primitive version, at the cost of a slower running
time. We state this in the next two lemmas; these are essentially shown in
[KLM89], but we include a proof in the appendix for completeness.

######  Lemma 2.16.

An unbiased estimator of $u_{F}(p)$ with relative variance at most $1$ can be
computed in time $O(NM^{2})$.

######  Lemma 2.17 (DNF sampling).

There exists an algorithm that draws a sample of values in time $O(NM^{2})$
according to the following distribution: Each variable independently takes
value True with probability $p$ and False with probability $1-p$, conditioned
on the fact that the values satisfy $F$.

##  3 Random Contraction with Large Edge Enumeration

In this section, we design an $m^{O(\log n)}$-time algorithm that outputs an
unbiased estimator of $u_{G}(p)$ with relative variance $O(1)$. It follows by
Lemma 2.7 that a $(1\pm\epsilon)$-approximation can be computed in $m^{O(\log
n)}\varepsilon^{-2}$ time, thereby establishing Theorem 1.1.

###  3.1 Algorithm Description

##### Overview.

The algorithm is recursive. Before describing the algorithm formally, we give
some intuition for the recursive step. The recursive case is divided into two
sub-cases depending on the maximum rank of the hyperedges. We call a
hypergraph _universally small_ if all edge ranks are at most $n/2$; otherwise,
it is said to be _existentially large_. If the hypergraph is universally
small, the algorithm runs a single recursive step of random hyperedge
contraction, and recursively estimates the unreliability of the contracted
hypergraph. This is repeated $\mathrm{poly}(n)$ times to reduce the variance
of the estimator, and the average of all estimates is taken as output. If the
hypergraph is existentially large, the algorithm lists all large hyperedges of
rank greater than $n/2$, enumerates the first large hyperedge in the list that
does not fail, and recursively estimates the unreliability of the resulting
subgraph. The algorithm also handles the case that all large hyperedges fail
by recursing on the (universally small) sub-hypergraph formed by deleting all
large edges.

Now, we describe the algorithm formally.

1 $n\leftarrow|V|,\lambda\leftarrow$ minimum cut value of $G$ computed by
Theorem 2.1.

2 if  _$G$ is disconnected_ then

3 return 1\.

4 end if

5if  _$p^{\lambda}\geq n^{-10}$_ then

6 Run the Monte Carlo sampling algorithm.

7 end if

8if  _$n\leq O(1)$_ then

9 Merge parallel hyperedges into a weighted hyperedge.

10 Enumerate all $2^{m}$ possible outcomes of random hyperedge removal, where
$m\leq 2^{n}$ is the number of weighted hyperedges.

11 return the total probability that the hypergraph is disconnected after
random hyperedge removal, where a hyperedge of weight $w(e)$ has failure
probability $p^{w(e)}$.

12 end if

13if  _$G$ is universally small_ then

14 $q\leftarrow n^{-10/\lambda}$

15 for  _$i=1$ to $2n^{12}$_ do

16 Sample $H_{i}\sim G(q)$.

17 Recursively call Unreliability$(H_{i},p/q)$ to get estimator $X_{i}$.

18 end for

19 return the average of all $X_{i}$’s.

20else

21 List large hyperedges $e_{1},e_{2},\ldots,e_{\ell}$. Let $E_{i}$ be the set
of first $i$ hyperedges in the list.

22 for  _$i=0$ to $\ell-1$_ do

23 Recursively call Unreliability$(H_{i}=(G-E_{i})/e_{i+1},p)$ to get
estimator $X_{i}$.

24 end for

25 Recursively call Unreliability$(H_{\ell}=G-E_{\ell},p)$ to get estimator
$X_{\ell}$.

26 return $p^{\ell}\cdot X_{\ell}+\sum_{i=1}^{\ell}p^{i}(1-p)\cdot X_{i}$.

27 end if

Algorithm 1 Unreliability$(G=(V,E),p)$

##### Base cases.

There are three base cases:

  1. 1.

$G$ is disconnected. In this case, we output 1.

  2. 2.

$p$ is larger than $n^{-10/\lambda}$. In this case, we use Monte Carlo
sampling (Lemma 2.13) and take average of $n^{10}$ samples.

  3. 3.

The number of vertices $n$ is a constant. In this case, we merge all parallel
hyperedges to form weighted hyperedges. We need to estimate $u_{G}(p)$ when
each weighted hyperedge $e$ is removed with probability $p^{w(e)}$, where
$w(e)$ is the weight of $e$. We enumerate over all possible subsets of
weighted hyperedges that are deleted, and compute $u_{G}(p)$ exactly. The
first step takes $O(m)$ time; the rest is $O(1)$ time. We have established the
following lemma:

######  Lemma 3.1.

When $n=O(1)$, $u_{G}(p)$ can be exactly computed in $O(m)$ time.

##### Recursive case.

We start by classifying hypergraphs as follows:

######  Definition 3.2 (universally small, existentially large hypergraphs).

A hypergraph is _universally small_ if all hyperedges are of rank at most
$n/2$. A hypergraph is _existentially large_ if there exists a hyperedge of
rank greater than $n/2$.

##### Recursive algorithm for universally small hypergraphs.

The algorithm repeats a random contraction step independently $2n^{12}$ times.
In the $i$-th random contraction step, the algorithm samples $H_{i}\sim G(q)$
by contracting each edge with probability $1-q$ independently, where
$q=n^{-10/\lambda}$. Note that $q\geq p$, otherwise we are in a base case.
Then, the algorithm recursively estimates $u_{H_{i}}(p/q)$. We will show later
that $u_{H_{i}}(p/q)$ is an unbiased estimator of $u_{G}(p)$ with bounded
relative variance. After all $2n^{12}$ recursive calls, the algorithm takes
the average of the estimators returned by these recursive calls to be the
output.

##### Recursive algorithm for existentially large hypergraphs.

Suppose there are $\ell$ large hyperedges, ordered arbitrarily as
$e_{1},e_{2},\ldots,e_{\ell}$. Let $E_{i}$ be the subset of first $i$
hyperedges in the list; in particular, $E_{0}=\emptyset$. We divide the event
of hypergraph disconnection into $\ell+1$ disjoint events by enumerating the
first hyperedge in the list that does not fail. Formally, for
$i=0,1,\ldots,\ell-1$, let $A_{i}$ be the event that first $i$ hyperedges in
the list all fail, but the $(i+1)$-th hyperedge survives; Let $A_{\ell}$ be
the event that all $\ell$ hyperedges fail. Then $\Pr[A_{i}]=p^{i}(1-p)$ for
$i\leq\ell-1$ and $\Pr[A_{\ell}]=p^{\ell}$. Conditioned on each event $A_{i}$,
we can remove the failed hyperedges in $E_{i}$ and contract the first
surviving hyperedge $e_{i+1}$ to form a subgraph $H_{i}$. Formally, let
$H_{i}=(G-E_{i})/e_{i+1}$ for $i=0,1,\ldots,\ell-1$, and
$H_{\ell}=G-E_{\ell}$. The event that $G$ disconnects conditioned on $A_{i}$
is equivalent to $H_{i}$ disconnecting when each hyperedge is removed with
probability $p$ independently. We have

$u_{G}(p)=\sum_{i=0}^{\ell}\Pr[A_{i}]\cdot\Pr[G\text{
disconnects}|A_{i}]=p^{\ell}\cdot
u_{H_{\ell}}(p)+\sum_{i=0}^{\ell-1}p^{i}(1-p)\cdot u_{H_{i}}(p)$ (1)

The algorithm runs $\ell+1=O(m)$ recursive calls on each $H_{i}$ to get
unbiased estimators $X_{i}$ of $u_{H_{i}}(p)$. The overall estimator $X$ of
$u_{G}(p)$ is then given by $X=p^{\ell}\cdot
X_{\ell}+\sum_{i=0}^{\ell-1}p^{i}(1-p)\cdot X_{i}$. Equation (1) shows that
$X$ is an unbiased estimator of $u_{G}(p)$.

The subproblems are easier because of the following reason: in $H_{i}$ for
$i\leq\ell-1$, we contracted a large hyperedge from $G$, so the number of
vertices decreases by at least a half; In $H_{\ell}$, we removed all large
hyperedges from $G$, so $H_{\ell}$ is universally small.

###  3.2 Correctness

In this section, we prove the following lemma that establishes correctness of
the algorithm.

######  Lemma 3.3.

Algorithm 1 outputs an unbiased estimator with relative variance at most $1$.

Note that the base cases of disconnected $G$ and constant size output exact
value of $u_{G}(p)$, and the base case of Monte Carlo sampling outputs an
unbiased estimator of $u_{G}(p)$. Also, an enumeration step in the
existentially large case does not introduce variance. So, we only need to
bound the relative variance introduced in the universally small case. To do
so, we first analyze the variance introduced in a random contraction step.

The key to bounding relative variance of a random contraction step is the
following property of a random subgraph which we will prove later.

######  Lemma 3.4.

$p^{\lambda}\leq u_{G}(p)\leq n^{2}p^{\lambda}$.

Lemma 3.4 provides an upper bound on the relative variance of random
contraction:

######  Lemma 3.5.

Suppose $H\sim G(q)$ and $q\geq p$. Then, the relative variance of
$u_{H}(p/q)$ is at most $n^{2}q^{-\lambda}-1$.

###### Proof.

Because $H$ is constructed by contraction from $G$, its min-cut value
$\lambda_{H}$ is at least the min-cut value $\lambda$ in $G$. By Lemma 3.4,

$u_{H}(p/q)\leq|V(H)|^{2}(p/q)^{\lambda_{H}}\leq n^{2}(p/q)^{\lambda}$ (2)

because $|V(H)|\leq n$, $\lambda_{H}\geq\lambda$, and $q\geq p$.

$u_{H}(p/q)$ is an unbiased estimator of $u_{G}(p)$ by Lemma 2.2. Next we
bound its relative variance $\eta[u_{H}(p/q)]$. By Fact 2.9, the relative
variance is upper bounded by $\frac{\max_{H}u_{H}(p/q)}{u_{G}(p)}-1$. We have
$\max_{H}u_{H}(p/q)\leq n^{2}(p/q)^{\lambda}$ by Equation (2), and
$u_{G}(p)\geq p^{\lambda}$ by Lemma 3.4. Therefore,

$\eta[u_{H}(p/q)]\leq\frac{n^{2}(p/q)^{\lambda}}{p^{\lambda}}-1=n^{2}q^{-\lambda}-1.\qed$

We are now prepared to prove Lemma 3.3.

###### Proof of Lemma 3.3.

We will prove the lemma by induction on number of vertices $n$, number of
hyperedges $m$, as well as the value of $\left\lceil
m\ln\frac{1}{p}\right\rceil$. The base case of $n=O(1)$ is given by Lemma 3.1.
The base case of $m=0$ is handled by the disconnected case in the algorithm.
These two base cases output the exact value of $u_{G}(p)$. For the induction
on $\left\lceil m\ln\frac{1}{p}\right\rceil$, notice that this value is a
positive integer because $p\in(0,1)$ in all recursive calls. The base case
$\left\lceil m\ln\frac{1}{p}\right\rceil\leq\frac{10m\ln n}{\lambda}$ implies
$p^{\lambda}\geq n^{-10}$. Hence, it is handled by Monte Carlo sampling in the
algorithm, which outputs an unbiased estimator of $u_{G}(p)$ with relative
variance at most $\frac{1}{u_{G}(p)}\leq\frac{1}{p^{\lambda}}\leq n^{10}$ by
Lemma 2.13. After taking average of $n^{10}$ samples, the relative variance is
reduced to at most $1$ by Fact 2.4.

For the inductive step, there are two cases. We first consider a random
contraction step when the hypergraph is universally small. This step generates
$2n^{12}$ random subgraphs $H_{i}\sim G(q)$, where $q^{\lambda}=n^{-10}$.
Lemma 2.2 gives that $u_{H_{i}}(p/q)$ is an unbiased estimator of $u_{G}(p)$.
Lemma 3.5 gives that $u_{H_{i}}(p/q)$ has relative variance at most
$n^{2}q^{-\lambda}-1=n^{12}-1$. By the inductive hypothesis, each subproblem
returns an unbiased estimator $X_{i}$ of $u_{H_{i}}(p/q)$ with relative
variance at most $1$. By Fact 2.5, $X_{i}$ is an unbiased estimator of
$u_{G}(p)$ with relative variance at most $n^{12}(1+1)-1\leq 2n^{12}$. Taking
average over all $2n^{12}$ estimators, $X_{i}$ gives an unbiased estimator of
$u_{G}(p)$ with relative variance at most $1$ by Fact 2.4.

Next, we consider a large hyperedge enumeration step when the input hypergraph
is existentially large. The algorithm computes an estimator $X=p^{\ell}\cdot
X_{\ell}+\sum_{i=1}^{\ell}p^{i}(1-p)\cdot X_{i}$, where $X_{i}$’s are returned
by recursive calls on $H_{i}$. By the inductive hypothesis, the recursive
calls give unbiased estimators, i.e. $\mathbb{E}[X_{i}]=u_{H_{i}}(p)$. We have

$\mathbb{E}[X]=p^{\ell}\cdot\mathbb{E}[X_{\ell}]+\sum_{i=1}^{\ell}p^{i}(1-p)\cdot\mathbb{E}[X_{i}]=p^{\ell}\cdot
u_{H_{\ell}}(p)+\sum_{i=0}^{\ell-1}p^{i}(1-p)\cdot u_{H_{i}}(p)=u_{G}(p)$

where the last step is by Equation (1).

$X$ is a convex combination of independent recursive estimators $X_{i}$, which
have relative variance at most $1$ by the inductive hypothesis. Hence, $X$
also has relative variance at most $1$ by Fact 2.8.

Finally, we argue that the induction is valid, i.e., that we always make
progress on one of the inductive parameters in every recursive call. Whenever
a hyperedge is contracted or deleted, we decrease $n$ or $m$. It is possible
that a random contraction step does not change the hypergraph. In that case,
notice that $p$ is changed to $p/q$ in the subproblem. So, $m\ln\frac{1}{p}$
decreases by $m\ln\frac{1}{q}=\frac{10m\ln n}{\lambda}\geq 10$. Therefore, we
also decrease $\left\lceil m\ln\frac{1}{p}\right\rceil$, and the induction is
valid. ∎

In the rest of this subsection, we give a proof of our main technical lemma,
Lemma 3.4.

##### Proof of Lemma 3.4

The lower bound of $p^{\lambda}$ in Lemma 3.4 holds because a minimum cut
fails with probability $p^{\lambda}$. The rest of the proof is devoted to the
upper bound of $n^{2}p^{\lambda}$.

We first assume that in the hypergraph $G$, the hyperedges are partitioned
into pairs of parallel hyperedges. This is w.l.o.g. because we can replace
each hyperedge by two copies and change the failure probability $p$ to
$\sqrt{p}$.

We introduce some definitions that are used only in the analysis (i.e., the
algorithm does not need to compute them). For any contracted hypergraph of
$G$, we choose an orientation of the hyperedges in the sense that in each
hyperedge, one vertex is designated the head and all other vertices are tails.
We require the orientation to satisfy the property that any pair of parallel
hyperedges (in the partition of hyperedges into pairs) have different heads.
This is always possible because the rank of each hyperedge is at least 2.
Besides this property, the choice of heads are arbitrary. The orientation is
chosen in a consistent way. That is, any fixed contracted hypergraph always
chooses the same orientation throughout the analysis.

The orientation is used to define representatives of contracted supervertices.
Each contracted supervertex during the contraction process will be assigned a
representative vertex, which is an original vertex contracted into the
supervertex. Initially, each vertex is its own representative. Whenever a
hyperedge $e$ is contracted, we assign the representative of the head of $e$
to be the representative of the new contracted supervertex.

######  Claim 3.6.

For any pair of supervertices $u\neq v$ in a contracted hypergraph of $G$,
there are at least $\lambda$ hyperedges that contain at least one of $u$ or
$v$ as a tail.

###### Proof.

Consider any pair of supervertices $u,v$. The (undirected) degree cut of $u$
(denoted $\partial u$) and degree cut of $v$ (denoted $\partial v$) are cuts
in the original hypergraphs, and have cut value at least $\lambda$. The
hyperedges in the degree cuts are pairs of parallel hyperedges. For a pair in
$\partial u\setminus\partial v$, at least one copy contains $u$ as a tail.
Similarly, for a pair in $\partial v\setminus\partial u$, at least one copy
contains $v$ as a tail. Finally, for a hyperedge in $\partial u\cap\partial
v$, it contains both $u$ and $v$. The hyperedge only has one head, so either
$u$ or $v$ is a tail. Therefore, there are at least

$\frac{1}{2}(|\partial u\setminus\partial v|+|\partial v\setminus\partial
u|)+|\partial u\cap\partial v|=\frac{1}{2}(|\partial u|+|\partial
v|)\geq\lambda$

hyperedges that contain $u$ or $v$ as a tail. ∎

We now proceed to prove the upper bound.

##### Exponential contraction process.

For the sake of analysis, consider the following continuous time random
process called the exponential contraction process. Let each hyperedge $e$
independently arrive at a time $Y_{e}$ following the exponential distribution
of rate $1$. Then, the probability that a hyperedge does not arrive before
time $\ln\frac{1}{q}$ is $e^{-\ln\frac{1}{q}}=q$. Therefore, contracting
hyperedges that arrive before time $\ln\frac{1}{q}$ produces the same
distribution as $H\sim G(q)$.

In the contraction process, if the hypergraph is not contracted into a single
supervertex at time $\ln\frac{1}{p}$ (which happens with probability
$u_{G}(p)$), there are at least two supervertices. Consequently, at least two
vertices survive as representatives. We will show that the probability that
any pair of vertices $s,t$ both survive is at most $p^{\lambda}$. By union
bounding over all ${n\choose 2}\leq n^{2}$ pairs of vertices, we have
$u_{G}(p)\leq n^{2}p^{\lambda}$ which completes the proof.

To bound the probability that any pair of vertices $s,t$ both survive, we
choose a set of _critical edges_ during the contraction process as follows.
When $s$ and $t$ are in different supervertices $\widetilde{s}$ and
$\widetilde{t}$, we choose $\lambda$ hyperedges that contain at least one of
$\widetilde{s}$ or $\widetilde{t}$ as a tail guaranteed by 3.6; otherwise, we
choose $\lambda$ arbitrary edges. (The critical edges may change after each
contraction.) Note that whenever a critical edge arrives, one of $s$ or $t$ is
no longer a representative. Hence, if $s,t$ both survive as representatives
after the contraction process, then no critical edge arrives during the
contraction process. By Lemma 3.7, this happens with probability at most
$e^{-\lambda\ln\frac{1}{p}}=p^{\lambda}$.

######  Lemma 3.7.

Suppose during the exponential contraction process from time 0 to $T$, we
maintain a subset of uncontracted hyperedges called the _critical edges_. The
critical edges could change immediately after each arrival of an uncontracted
hyperedge, but do not change between two arrivals. Suppose that there are
always at least $\lambda$ critical edges. Then, the probability that no
critical edge arrives up to time $T$ is at most $e^{-\lambda T}$.

###### Proof.

The proof is by induction on the number of uncontracted hyperedges $m$. The
base case is $m=\lambda$, where the set of critical edges cannot change, and
the probability that no critical edge arrives is $e^{-\lambda T}$.

For the inductive case, let $m_{\mathrm{crit}}\geq\lambda$ be the current
number of critical edges. We bound the probability that no critical edge
arrives up to time $T$ (denoted $p_{G}(T)$) by integrating over the earliest
time $t$ that a hyperedge $e_{i}$ arrives. By Fact 2.12, $t$ follows the
exponential distribution of rate $m$, and $e_{i}$ is not a critical edge with
probability $1-\frac{m_{\mathrm{crit}}}{m}$. After the earliest hyperedge
$e_{i}$ arrives, we apply the inductive hypothesis on hypergraph $G/e_{i}$ and
remaining time $T-t$.

$\displaystyle p_{G}(T)$
$\displaystyle=\int_{0}^{T}me^{-mt}\mathrm{d}t\cdot\left(1-\frac{m_{\mathrm{crit}}}{m}\right)\cdot
p_{G/e_{i}}(T-t)+\int_{T}^{\infty}me^{-mt}\mathrm{d}t\cdot 1$
$\displaystyle\leq
e^{-mT}+\int_{0}^{T}me^{-mt}\mathrm{d}t\cdot\left(1-\frac{\lambda}{m}\right)\cdot
e^{-\lambda(T-t)}$ $\displaystyle=e^{-mT}+e^{-\lambda
T}\int_{0}^{T}(m-\lambda)e^{-(m-\lambda)t}\mathrm{d}t$
$\displaystyle=e^{-mT}+e^{-\lambda T}(1-e^{-(m-\lambda)T})=e^{-\lambda T},$

which completes the inductive case. ∎

###  3.3 Running Time

In this section, we prove the following lemma of running time of the
algorithm.

######  Lemma 3.8.

The expected running time of Algorithm 1 is $m^{O(\log n)}$.

##### Size decrease bound.

In order to bound the size of the recursion tree, we ideally want each random
contraction step to reduce the number of supervertices by a constant factor,
so that the recursion tree has depth $O(\log n)$. This does not generally hold
with high probability when some hyperedge’s rank is large. As an extreme
example, consider the hypergraph that consists of $n$ distinct hyperedges of
rank $n-1$. The probability to contract nothing is $q^{n}$, while the
contraction step is repeated $n^{2}q^{-\lambda}=n^{2}q^{-(n-1)}$ times, so we
expect to see at least one bad subproblem where the number of vertices does
not decrease. If this happens, then the size of the recursion tree would be
unbounded.

This is where the maximum rank assumption in the universally small case
becomes useful: we can control the probability to get a bad subproblem to be
small enough, which is crucial in bounding the size of the recursion tree.

######  Lemma 3.9.

Fix constants $A>B>1$. Suppose that all hyperedges have rank at most $R=n/A$,
and $n$ is larger than some constant depending on $A$. Let $n^{*}=\lceil
BR\rceil$, and let $H\sim G(q)$. Then, $\Pr[|V(H)|\geq
n^{*}+1]<n^{A^{2}/B}q^{B\lambda}$.

###### Proof.

Define $t(G)$ to be the stopping time in the contraction process when the
vertex size of the contracted hypergraph decreases to at most $n^{*}$. By
definition

$\Pr[|V(H)|>n^{*}]=\Pr\left[t(G)>\ln\frac{1}{q}\right].$

By Markov’s inequality,

$\Pr\left[t(G)>\ln\frac{1}{q}\right]=\Pr[e^{B\lambda\cdot
t(G)}>q^{-B\lambda}]\leq\frac{\mathbb{E}[e^{B\lambda\cdot
t(G)}]}{q^{-B\lambda}}=\mathbb{E}[e^{B\lambda\cdot t(G)}]q^{B\lambda}.\\\ $

By choosing the same parameters $A,B$ in Lemma 3.11 (which we will prove
later),

$\Pr\left[t(G)>\ln\frac{1}{q}\right]\leq\mathbb{E}[e^{B\lambda\cdot
t(G)}]q^{B\lambda}\leq\left(\frac{en}{n^{*}}\right)^{A\ln
n}q^{B\lambda}\leq(Ae/B)^{A\ln n}q^{B\lambda}\leq
n^{A(1+\ln\frac{A}{B})}q^{B\lambda}\leq n^{A^{2}/B}q^{B\lambda},$

where the last inequality uses that $1+\ln x\leq x$ for all $x\geq 0$. ∎

######  Corollary 3.10.

Assume that all hyperedges have rank at most $n/2$ and $n$ is larger than a
suitable constant. Let $H\sim G(q)$. Then, $\Pr[|V(H)|\geq 0.8n]\leq
n^{2.7}q^{1.5\lambda}$.

###### Proof.

In Lemma 3.9, set $A=2$ and $B=1.5$. We have $n^{*}+1=\lceil
1.5n/2\rceil+1\leq 0.8n$. Then, $\Pr[|V(H)|\geq
0.8n]<n^{8/3}q^{1.5\lambda}\leq n^{2.7}q^{1.5\lambda}$. ∎

######  Lemma 3.11.

Fix constants $A>B>1$. Suppose the maximum rank is upper bounded by $R$ and
$R$ is larger than some constant depending on $A$. For any hypergraph
$\widetilde{G}$ formed by contraction from $G$, define $t(\widetilde{G})$ to
be the following stopping time: In a contraction process starting at
$\widetilde{G}$, the vertex size of the contracted hypergraph decreases to at
most $n^{*}=\lceil BR\rceil$. Suppose $|V(\widetilde{G})|\leq N$, where
$N=AR$. Let $\widetilde{\lambda}$ be the min-cut value in $\widetilde{G}$.
Then,

$\mathbb{E}\left[e^{B\widetilde{\lambda}\cdot
t(\widetilde{G})}\right]\leq\max\left\\{\left(\frac{|V(\widetilde{G})|}{n^{*}/e}\right)^{A\ln
N},1\right\\}.$

###### Proof.

Our proof is by induction on $\widetilde{n}=|V(\widetilde{G})|$. As the base
case, when $\widetilde{n}\leq n^{*}$, by definition $t(\widetilde{G})=0$ and
$e^{B\widetilde{\lambda}\cdot t(\widetilde{G})}=1$, so the statement holds.

Next consider the inductive step where $\widetilde{n}>n^{*}$. Let
$\bar{r}=\frac{1}{\widetilde{m}}\sum_{e\in E(\widetilde{G})}r(e)$ be the
average rank in $\widetilde{G}$, where $\widetilde{m}=|E(\widetilde{G})|$.

Let $\tau=\min_{e\in E(\widetilde{G})}X_{e}$ be the earliest arrival time of a
hyperedge in $\widetilde{G}$. Because the $X_{e}$’s are sampled from i.i.d.
exponential distributions of rate 1, the random variable $\tau$ follows the
exponential distribution of rate $\widetilde{m}$ by Fact 2.12. Note that any
degree cut in $\widetilde{G}$ has value at least the min-cut value
$\widetilde{\lambda}$ in $\widetilde{G}$. By summing over degrees of all
vertices, we have

$\widetilde{n}\widetilde{\lambda}\leq\sum_{e\in
E(\widetilde{G})}r(e)=\widetilde{m}\bar{r}\implies\widetilde{m}\geq\frac{\widetilde{n}\widetilde{\lambda}}{\bar{r}}.$

Denote $\mathrm{rate}(\cdot)$ to be the rate of a exponential distributed
random variable. Because $\widetilde{n}>n^{*}$ and $\bar{r}\leq R$, we have
$\text{rate}(\tau)=\widetilde{m}\geq\frac{\widetilde{n}\widetilde{\lambda}}{\bar{r}}>\frac{n^{*}\widetilde{\lambda}}{R}\geq
B\widetilde{\lambda}$.

By the moment generating function of the exponential distribution in Fact
2.10,

$\mathbb{E}\left[e^{B\widetilde{\lambda}\tau}\right]=\frac{1}{1-\frac{B\widetilde{\lambda}}{\text{rate}(\tau)}}\leq\frac{1}{1-\frac{B\widetilde{\lambda}}{\widetilde{n}\widetilde{\lambda}/\bar{r}}}=\frac{1}{1-\frac{B\bar{r}}{\widetilde{n}}}$
(3)

Now, consider the distribution of $t(\widetilde{G})$ after revealing $\tau$.
To decrease size from $\widetilde{n}>n^{*}$ to below the threshold $n^{*}$, at
least one hyperedge needs to be contracted; so $t(\widetilde{G})\geq\tau$.
Moreover, by the memoryless property of the exponential distribution in Fact
2.11, $\tau$ and $t(\widetilde{G})-\tau$ are independent. If we further reveal
the information that the hyperedge that arrives the earliest is $e_{i}$, then
we know the random process after the earliest arrival is equivalent to running
the contraction process starting from $\widetilde{G}/e_{i}$. Thus,
$t(\widetilde{G})-\tau$ follows the same distribution as
$t(\widetilde{G}/e_{i})$ conditioned on $e_{i}$ arrives first. Because the
hyperedges follow i.i.d. exponential distribution, they are equally likely to
arrive the earliest. Therefore, unconditionally we have that
$t(\widetilde{G})-\tau$ follows distribution of $t(\widetilde{G}/e_{i})$ for
each $e_{i}$ with probability $\frac{1}{\widetilde{m}}$. Formally,

$\mathbb{E}\left[e^{B\widetilde{\lambda}\cdot
t(\widetilde{G})}\right]=\mathbb{E}\left[e^{B\widetilde{\lambda}\tau}\right]\cdot\mathbb{E}\left[e^{B\widetilde{\lambda}(t(\widetilde{G})-\tau)}\right]=\mathbb{E}\left[e^{B\widetilde{\lambda}\tau}\right]\sum_{e_{i}\in
E(\widetilde{G})}\frac{1}{\widetilde{m}}\mathbb{E}\left[e^{B\widetilde{\lambda}\cdot
t(\widetilde{G}/e_{i})}\right]$ (4)

We now apply the inductive hypothesis to bound the term
$\mathbb{E}[e^{B\widetilde{\lambda}\cdot t(\widetilde{G}/e_{i})}]$ for each
$e_{i}$ separately. Note that the min-cut value $\lambda_{i}$ in
$\widetilde{G}/e_{i}$ is at least $\widetilde{\lambda}$ because a contraction
cannot decrease the min-cut value.

$\displaystyle\mathbb{E}\left[e^{B\widetilde{\lambda}\cdot
t(\widetilde{G}/e_{i})}\right]$
$\displaystyle\leq\mathbb{E}\left[e^{B\lambda_{i}\cdot
t(\widetilde{G}/e_{i})}\right]\leq\max\left\\{\left(\frac{\widetilde{n}-r(e_{i})+1}{n^{*}/e}\right)^{A\ln
N},1\right\\}$
$\displaystyle=\frac{(\max\\{\widetilde{n}-r(e_{i})+1,n^{*}/e\\})^{A\ln
N}}{(n^{*}/e)^{A\ln
N}}\leq\frac{(\max\\{\widetilde{n}-r(e_{i})+1,\widetilde{n}/e\\})^{A\ln
N}}{\widetilde{n}^{A\ln
N}}\cdot\left(\frac{e\widetilde{n}}{n^{*}}\right)^{A\ln N}$
$\displaystyle=\max\left\\{\left(1-\frac{r(e_{i})-1}{\widetilde{n}}\right)^{A\ln
N},N^{-A}\right\\}\cdot\left(\frac{e\widetilde{n}}{n^{*}}\right)^{A\ln N}.$

Next, we prove that $\max\\{(1-\frac{r-1}{\widetilde{n}})^{A\ln
N},N^{-A}\\}\leq 1-\frac{Br}{\widetilde{n}}$ for all $r\in[2,R]$. For the
second term, we have $N^{-A}<\frac{1}{N}$, while

$1-\frac{Br}{\widetilde{n}}\geq 1-\frac{BR}{\widetilde{n}}\geq
1-\frac{n^{*}}{n^{*}+1}=\frac{1}{n^{*}+1}\geq\frac{1}{N}.$

For the first term, define $x=\frac{r(e_{i})-1}{\widetilde{n}}$ in terms of
$r(e_{i})$, which satisfies
$x\in[\frac{1}{\widetilde{n}},\frac{R-1}{\widetilde{n}}]$. Then,
$r(e_{i})=\widetilde{n}x+1$. We want to bound
$(1-\frac{r-1}{\widetilde{n}})^{A\ln N}\leq 1-\frac{Br}{\widetilde{n}}$ for
all $r\in[2,R]$, which is equivalent to

$(1-x)^{A\ln N}\leq 1-Bx-\frac{B}{\widetilde{n}}.$ (5)

Note that the LHS is convex on $(0,1)$ when $A\ln N\geq 2$, and the RHS is
linear. So we only need to prove (5) for the two endpoints
$x=\frac{1}{\widetilde{n}}$ and $x=\frac{R-1}{\widetilde{n}}$. For
$x=\frac{1}{\widetilde{n}}$, we have

$\left(1-\frac{1}{\widetilde{n}}\right)^{A\ln N}\leq e^{-A\ln
N/\widetilde{n}}\leq 1-\frac{A\ln N}{2\widetilde{n}}\leq
1-\frac{2B}{\widetilde{n}}$

Here, the second inequality is by $e^{-x}\leq 1-\frac{x}{2}$ for $x\in[0,1]$
or $A\ln N/\widetilde{n}\leq 1$, which holds when $N$ is larger than some
constant (depending on $A$). The last inequality holds when $\ln N\geq 4$.

Next, we consider the second endpoint $x=\frac{R-1}{\widetilde{n}}$. The
assumption $N=AR\geq\widetilde{n}$ implies
$\frac{R}{\widetilde{n}}\geq\frac{1}{A}$. So, we have

$\left(1-\frac{R-1}{\widetilde{n}}\right)^{A\ln
N}\leq\left(1-\frac{1}{A}+\frac{1}{\widetilde{n}}\right)^{A\ln
N}\leq\frac{1}{N}$

Here, the last inequality is equivalent to
$1-\frac{1}{A}+\frac{1}{\widetilde{n}}\leq e^{-1/A}$, which holds when
$\widetilde{n}>3A^{2}$ and $A>1$.

Now, we have

$\mathbb{E}\left[e^{B\widetilde{\lambda}\cdot
t(\widetilde{G})}\right]\stackrel{{\scriptstyle(\ref{eq:NBt-
induction})}}{{=}}\mathbb{E}\left[e^{B\widetilde{\lambda}\tau}\right]\cdot\frac{1}{\widetilde{m}}\sum_{e_{i}\in
E(\widetilde{G})}\mathbb{E}\left[e^{B\widetilde{\lambda}\cdot
t(\widetilde{G}/e)}\right]\stackrel{{\scriptstyle(\ref{eq:NBtau})}}{{\leq}}\frac{1}{1-\frac{B\bar{r}}{\widetilde{n}}}\cdot\frac{1}{\widetilde{m}}\sum_{e_{i}\in
E(\widetilde{G})}\mathbb{E}\left[e^{B\widetilde{\lambda}\cdot
t(\widetilde{G}/e)}\right]$
$\leq\frac{1}{1-\frac{B\bar{r}}{\widetilde{n}}}\cdot\frac{1}{\widetilde{m}}\sum_{e_{i}}\left(1-\frac{Br(e_{i})}{\widetilde{n}}\right)\cdot\left(\frac{e\widetilde{n}}{n^{*}}\right)^{A\ln
N}\leq\left(\frac{e\widetilde{n}}{n^{*}}\right)^{A\ln N}$

which establishes the inductive case. ∎

##### Proof of Lemma 3.8

We color each recursive call as black or red. Intuitively, they represent a
“success” or “failure” in recursive calls respectively. A call is black if it
decreases size by a constant factor, more precisely when $|V(H)|\leq 0.8n$.
Otherwise, the call is red.

The recursion tree has the following properties:

  1. 1.

Each subproblem makes at most $M=m^{O(1)}$ recursive calls. This is guaranteed
by the algorithm.

  2. 2.

The algorithm reaches base case after $O(\log n)$ black recursive calls. This
is because each black recursive call decreases $n$ by a constant factor, and
$O(\log n)$ black calls reduces $n$ to a constant, which is a base case.

  3. 3.

For each subproblem, the expected number of red recursive calls is at most
$1/2$. This is because in random contraction, we have $O(n^{2}q^{-\lambda})$
recursive calls, and each call fails (to get size decrease) with probability
at most $n^{2.7}q^{1.5\lambda}$ by Corollary 3.10. The expected number of red
calls is their product, which is upper bounded by $n^{4.7}q^{0.5\lambda}=o(1)$
when $q^{\lambda}=n^{-10}$.

Lemma 3.12 below shows that these properties give a upper bound of $m^{O(\log
n)}$ on the number of recursive calls. If we charge the time of sampling a
random contracted hypergraph to the subproblem on the contracted hypergraph,
then each subproblem spends $O(nm)$ time outside the recursive calls.
Therefore, the overall expected running time is $m^{O(\log n)}$. This
concludes the proof of Lemma 3.8.

Figure 1: A depiction of a portion of the computation tree. The failed
recursive calls are shown in dashed red, while the successful ones are shown
in solid black. Lemma 3.12 analyzes the expected size of the recursion tree.

######  Lemma 3.12.

Suppose in a randomly growing tree, each node $u$ is either a leaf, or has
$M(u)\leq M$ children, where $M=\Omega(n)$ is a parameter. Each edge from $u$
to its children is colored red with probability $f(u)$ such that
$M(u)f(u)\leq\theta=\frac{1}{2}$, and black otherwise. The different children
at a parent node are independent (including independence betwen the parent-
child edges); Also, a subtree is independent of everything outside the
subtree. Moreover, on any path from root to leaf, there can be at most $L$
black edges. Then, the expected number of nodes in the tree is at most
$M^{O(L)}$.

###### Proof.

We say a node $w$ is a red descendant of node $u$ if $u$ is an ancestor of
$w$, and the path from $u$ to $w$ is formed by red edges only. See Figure 1
for an illustration.

Let $K$ be the number of red descendants of some node $u$. Let $K_{i}$ be the
number of red descendants of $u$ that are $i$ steps deeper than $u$, so that
$K=\sum_{i\geq 1}K_{i}$. We have $\mathbb{E}[K_{1}]=M(u)f(u)\leq\theta$.
Inductively, suppose at level $i$, there are $K_{i}$ red descendants
$\\{u_{1},\ldots,u_{k_{i}}\\}$. By definition, the red descendants in level
$i+1$ must be children of red descendants in level $i$. Each $u_{j}$ will
generate at most $\theta$ red edges in expectation. So,
$\mathbb{E}[K_{i+1}]\leq\theta\cdot\mathbb{E}[K_{i}]$. By induction,
$\mathbb{E}[K_{i}]\leq\theta^{i}$. Note that the sum $\sum_{i\geq
1}\theta^{i}=\frac{\theta}{1-\theta}\leq 1$ converges and $K_{i}$’s are
nonnegative, so we can apply Fubini’s theorem to get

$\mathbb{E}[K]=\mathbb{E}\left[\sum_{i\geq 1}K_{i}\right]=\sum_{i\geq
1}\mathbb{E}[K_{i}]\leq\sum_{i\geq 1}\theta^{i}\leq 1.$

Let $V_{i}$ be the set of nodes that have $k$ black edges from the root. We
prove by induction that $\mathbb{E}[|V_{k}|]\leq 2(2M)^{k}$. It follows that
the expected number of nodes is
$\mathbb{E}[\sum_{k=0}^{L}|V_{k}|]=O((2M)^{L})=M^{O(L)}$. The base case for
$k=0$ is the expected number of red descendants of the root, as well as the
root itself, which is at most $1+1=2=2(2M)^{0}$. Next consider the inductive
step. For any node $w\in V_{k+1}$, let $(u,v)$ be the black edge closest to
$w$ on the path from root to $w$. Then, $u\in V_{k}$, and $w$ is either a red
descendent of $v$ or $v$ itself. Each node $u$ in $V_{k}$ generates $M(u)$
children $v$, and each $v$ generates at most $1$ red descendants in
expectation. Therefore, $\mathbb{E}[|V_{k+1}|]\leq\mathbb{E}[|V_{k}|]\cdot
M\cdot(1+1)\leq 2(2M^{k+1})$. ∎

##  4 Random Contraction with DNF Sampling

In this section, we strengthen the previous algorithm to obtain a running time
of $m\cdot n^{O(\log n\cdot\log\log\frac{1}{\delta})}$, at the cost of an
additive error of $\delta$, i.e. the output estimator is within
$(1\pm\varepsilon)u_{G}(p)\pm\delta$ whp (Theorem 1.2). When
$\delta=2^{-\mathrm{poly}(n)}$, the running time of the algorithm is $m\cdot
n^{O(\log^{2}n)}$. We show that the algorithm outputs an estimator of
$u_{G}(p)$ with bias at most $\delta$ and $\delta$-capped relative variance
$O(1)$. Theorem 1.2 then follows by Lemma 2.7.

We denote $N=\log_{2}\frac{1}{\delta}$. We can assume wlog $N\geq\log_{2}n$,
i.e. $\delta\leq\frac{1}{n}$. This is because we can run a simple Monte Carlo
simulation when $\delta\geq\frac{1}{n}$ in $O\left(\frac{\log
n}{\delta\varepsilon^{2}}\cdot
nm\right)=\widetilde{O}(n^{2}m\varepsilon^{-2})$ time by Lemma 2.14.

###  4.1 Algorithm Description

The algorithm is recursive. We start by defining the simple base cases. Then,
we introduce the definition of large hyperedges, which characterize the last
base case. Finally, we define the recursive cases.

####  4.1.1 Base Cases

There are four base cases, three of which are the following:

  1. 1.

When the number of vertices $n$ is a constant, we enumerate all possible
outcomes by brute force, which is identical to Lemma 3.1.

  2. 2.

When the hypergraph is already disconnected, output 1.

  3. 3.

When $p^{\lambda}<2^{-3N}$, output 0.

These three base cases are deterministic. The algorithms for the first two
base cases return the exact value of $u_{G}(p)$. The third case has an
additive bias of $u_{G}(p)$, which is at most $n^{2}p^{\lambda}$ by Lemma 3.4.
We assumed $N\geq\log_{2}n$ and $p^{\lambda}<2^{-3N}$, so
$n^{2}p^{\lambda}\leq(2^{N})^{2}\cdot 2^{-3N}\leq 2^{-N}\leq\delta$.

The fourth base case is called full revelation; it will be described later in
the section.

####  4.1.2 Large and Small Hyperedges

Before proceeding with the formal description of the remaining algorithm, let
us provide some intuition. Recall from Algorithm 1 that the large hyperedges
are the bottleneck in the random contraction algorithm: we branch $m$ times to
halve the number of vertices, which leads to the $m^{O(\log n)}$ running time.
However, if we ignore the small hyperedges and consider the hypergraph with
large hyperedges only, it turns out that the structure of cuts becomes much
simpler. This motivates us to partition the set of hyperedges $E$ into two
sets, $E_{\mathrm{large}}$ and $E_{\mathrm{small}}$. Intuitively, these are
sets of hyperedges of large and small rank respectively, but for technical
reasons, the precise definition needs to be more nuanced.

We now formally define the set $E_{\mathrm{large}}$. It depends on _phase
nodes_ in the recursive computation tree, which we define first. Initially,
the root of the computation tree is a phase node. For any non-root node $w$ of
the computation tree, let $u$ be the closest ancestor node of $w$ that is a
phase node (which exists because the root is a phase node). $w$ is a phase
node if and only if the number of vertices $n_{u}$ in $u$ and $n_{w}$ in $w$
satisfy $n_{w}\leq 0.8n_{u}$. If $w$ is not a phase node, such a $u$ is called
the _phase ancestor_ of $w$. Define a _phase_ with phase node $u$ to be all
computation nodes whose phase ancestor if $u$, as well as $u$ itself. See
Figure 2 for an illustration.

Given the definition of phase nodes, we define $E_{\mathrm{large}}$ as
follows: In a phase node, $E_{\mathrm{large}}$ is the set of all hyperedges of
rank $>n/2$. In a non-phase node $w$, $E_{\mathrm{large}}$ is inherited from
its phase ancestor $u$, i.e. the set of all hyperedges of rank $>n_{u}/2$ in
$u$. Let $G_{\mathrm{large}}$ denote the hypergraph
$(V(G),E_{\mathrm{large}})$. We let $E_{\mathrm{small}}$ be the complement set
of hyperedges $E\setminus E_{\mathrm{large}}$, and
$G_{\mathrm{small}}=(V(G),E_{\mathrm{small}})$.

Figure 2: A depiction of phases in the computation tree. The filled in nodes
are phase nodes. The blue and green nodes respectively root the blue and green
phases. Each phase can contain successful recursive steps, shown by solid
black edges and black nodes, and failed recursive steps, shown by dashed red
edges and red nodes. In a phase, every node has a phase ancestor which is the
root node of the phase; for instance, $u$ is the phase ancestor of $v$ (and of
every other node in the blue phase).

####  4.1.3 The Last Base Case: Full Revelation

We are now ready to describe the last base case that we call full revelation.
Let $\beta=\lambda-\lambda_{L}$, where $\lambda_{L}$ is the min-cut value in
$G_{\mathrm{large}}$. The last base case is invoked when $\beta<\lambda/N$.

The algorithm samples a random subgraph $H\sim G(p)$ conditioned on the event
that the contracted hyperedges in $E_{\mathrm{large}}$ do not contract the
whole hypergraph into a singleton. This is done in two steps. First, we write
a DNF formula for the disconnection event in $G_{\mathrm{large}}$, and apply
Lemma 2.17 to contract each hyperedge in $E_{\mathrm{large}}$ with probability
$1-p$ conditioned on the event that $G_{\mathrm{large}}$ is not contracted
into a single vertex. Second, we directly sample the remaining uncontracted
hyperedges in $E_{\mathrm{small}}$, that is we independently contract each of
those hyperedges with probability $1-p$. The resulting hypergraph $H$ follows
the desired distribution.

The algorithm repeats $8n^{2}$ independent samples of the above process to
obtain samples $H_{i}$, and estimates $X_{i}=0$ if $H_{i}$ is contracted into
a singleton, and $X_{i}=1$ otherwise. Let $X$ be the average of all these
estimators $X_{i}$. Next, we use the DNF counting algorithm in Lemma 2.16 to
get an unbiased estimator $Z$ of $u_{G_{\mathrm{large}}}(p)$. The product $XZ$
is the estimator of $u_{G}(p)$ output by the algorithm.

We are now left to describe the recursive step of the algorithm. For this
purpose, we need to first establish some properties of large edges:

####  4.1.4 Properties of Large Edges

The first property is that the association of $E_{\mathrm{large}}$ with large
ranks and $E_{\mathrm{small}}$ with small ranks is approximately correct:

######  Fact 4.1.

Any hyperedge in $E_{\mathrm{large}}$ has rank at least $0.3n$, and any
hyperedge in $E_{\mathrm{small}}$ has rank at most $0.7n$.

###### Proof.

Let $w$ be the current computation node. If $w$ is a phase node, then the fact
is by definition of $E_{\mathrm{large}}$. Else, let $u$ be the phase ancestor
of $u$. For any hyperedge $e\in E_{\mathrm{large}}(w)$,

$r_{w}(e)\geq r_{u}(e)-(n_{u}-n_{w})\geq 0.5n_{u}-0.2n_{u}=0.3n_{u}\geq
0.3n_{w}.$

For any hyperedge $e\in E_{\mathrm{small}}(w)$,

$r_{w}(e)\leq r_{u}(e)\leq 0.5n_{u}\leq\frac{0.5n_{w}}{0.8}\leq 0.7n_{w}.\qed$

The algorithm only contracts non-trivial hyperedges during recursion, i.e.,
hyperedges that are contracted into a singleton supervertex are removed. We
assert that all large hyperedges are candidates for contraction:

######  Fact 4.2.

Suppose $w$ is a non-phase node and $E_{\mathrm{large}}(w)$ is inherited from
the phase ancestor $u$ of $w$. Then, every hyperedge in
$E_{\mathrm{large}}(u)$ still appears in $E_{\mathrm{large}}(w)$, but may be
partially contracted.

###### Proof.

If there is a hyperedge $e$ in $E_{\mathrm{large}}(u)\setminus
E_{\mathrm{large}}(w)$, then that hyperedge is contracted to a single vertex
at node $w$. But then $n_{w}\leq n_{u}-r_{u}(e)+1\leq n_{u}/2$, so $w$ is a
phase node by definition, a contradiction. ∎

Finally, we come to the most important property, that of the simple structure
of cuts in $G_{\mathrm{large}}$. To explain this, let us introduce the
following property:

######  Definition 4.3 (pairwise intersecting property).

A set of hyperedges is _pairwise intersecting_ if any two hyperedges in the
set share at least one vertex.

Note that in particular, any set of hyperedges of rank $>n/2$ satisfy the
pairwise intersecting property because the sum of ranks of any two hyperedges
is more than $n$. We assert that this property continues to hold with our
modified definition of large hyperedges:

######  Fact 4.4.

The set of hyperedges $E_{\mathrm{large}}$ satisfies the pairwise intersection
property.

###### Proof.

By definition, $E_{\mathrm{large}}$ is either the set of hyperedges of rank
$>n/2$, or inherited from the phase ancestor $u$. In the former case, there
cannot be two disjoint hyperedges because their ranks sum to $>n$. In the
latter case, the property is inductively inherited from $u$. ∎

This allows us to conclude that $G_{\mathrm{large}}$ gets disconnected if and
only if any degree cut fails.

######  Lemma 4.5.

If a hypergraph $G$ satisfies the pairwise intersecting property, then $G$
disconnects if and only if some degree cut fails. In particular, by Fact 4.4,
this is true for $G_{\mathrm{large}}$.

###### Proof.

Let $H$ be the subgraph of surviving hyperedges. Consider $H$’s connected
components. Any non-singleton connected component must contain at least one
hyperedge. For any two non-singleton components, their hyperedges are
disjoint, which contradicts the pairwise intersecting property. Therefore,
there can only be at most one non-singleton connected component in $H$. $H$ is
either an empty hypergraph, i.e. no hyperedges, or it has one non-singleton
component with (zero or more) singletons. This means $H$ is disconnected if
and only if it contains an isolated singleton, which is further equivalent to
some degree cut failing in $G$. ∎

Now, the event of $G_{\mathrm{large}}$ getting disconnected can be written
into a DNF formula $F$, where each variable represents the failure of a
hyperedge and each clause represents the failure of a degree cut in
$G_{large}$ as the logical AND of the failure of all hyperedges in the cut.
$F$ has $n$ clauses and $m$ variables. Therefore, by Lemmas 2.16 and 2.17, we
have the following:

######  Lemma 4.6.

We can do the following in $O(n^{2}m)$ time:

  1. 1.

Compute an unbiased estimator of $u_{G_{\mathrm{large}}}(p)$ with relative
variance at most $1$.

  2. 2.

Sample a contracted hypergraph $H$ of $G_{\mathrm{large}}$ where every
hyperedge in $G_{\mathrm{large}}$ is contracted with probability $1-p$,
conditioned on the event that $H$ is not a singleton supervertex.

####  4.1.5 Recursive Cases

In universally small hypergraphs, the algorithm is identical to Algorithm 1.
We run random contraction with $q^{\lambda}=n^{-10}$, and repeat the step
$16n^{12}$ times.

The algorithm for the existentially large case is now different because we
cannot afford to enumerate $m$ events. Recall that when there exist large
hyperedges, the algorithm divides into two cases depending on the value of
$\beta=\lambda-\lambda_{L}$, where $\lambda_{L}$ is the min-cut value in
$G_{\mathrm{large}}$. When $\beta<\lambda/N$, we get full revelation that we
have already described as the last base case.

We call the remaining case when $\beta\geq\lambda/N$ _partial revelation_. In
that partial revelation case, the algorithm still runs a form of random
contraction, but only in a subspace of the entire probability space. We use
the parameter $\beta$ to control the speed of random contraction. By Lemma
4.5, $\lambda_{L}=\min_{u}d_{\rm large}(u)$, i.e., the minimum degree of a
vertex in $G_{\mathrm{large}}$. Intuitively, $\beta$ is used to control the
number of small hyperedges in each degree cut, which measures the speed of
random contraction when no large hyperedges get contracted. Note that
$0\leq\beta\leq\lambda$. Ideally, we want to decrease $\beta$ to as small as
$\lambda/N$, which reduces to the full revelation case. However, $\beta$ can
be non-monotone as both $\lambda$ and $\lambda_{L}$ can increase because of
contraction during recursion. So, we define another parameter $\gamma$ that
can be related to $\beta$ to bound the depth of recursion in a phase. Let
$\gamma=\ell-\lambda_{L}$, where $\ell=|E_{\mathrm{large}}|$ is the number of
large hyperedges. We show that unlike $\beta$, $\gamma$ is monotone in a
phase:

######  Lemma 4.7.

Suppose $v,w$ are nodes in the same phase. If $w$ is a descendant of $v$, then
$\gamma_{v}\geq\gamma_{w}$.

###### Proof.

Since $E_{\mathrm{large}}$ is the same set of hyperedges within a phase by
Fact 4.2, we have $\ell_{v}=\ell_{w}$. Now, since $w$ is a descendant of $v$,
the hypergraph $G_{\mathrm{large}}(w)$ is formed by contracting some set of
hyperedges in $G_{\mathrm{large}}(v)$. Hyperedge contractions cannot decrease
the value of the minimum cut; hence, $\lambda_{L}(w)\geq\lambda_{L}(v)$. The
lemma follows. ∎

##### Algorithm for partial revelation.

The algorithm runs random contraction at a more aggressive rate
$q^{\beta}=n^{-700}$.777The reason for this large polynomial in $n$ is as
follows. In the proof of Lemma 4.14, the algorithm needs to repeat the random
contraction $O(n^{4}q^{-\beta})$ times, and we show in Lemma 4.16 that each
trial has failure probability $n^{2}q^{1.01\beta}$. We need their product
$O(n^{6}q^{0.01\beta})$ to be $o(1)$, hence the choice $q^{\beta}=n^{-700}$.
This is done in two steps. First, we write a DNF formula for the disconnection
in $G_{\mathrm{large}}$, and apply Lemma 4.6 to contract each hyperedge in
$E_{\mathrm{large}}$ with probability $1-q$ conditioned on
$G_{\mathrm{large}}$ not being contracted into a singleton. Second, we
independently contract each uncontracted hyperedge in $E_{\mathrm{small}}$
with probability $1-q$. The resulting hypergraph $H$ follows the distribution
of $H\sim G(q)$ conditioned on the event that the contracted hyperedges in
$E_{\mathrm{large}}$ do not contract the whole hypergraph into a singleton.

The algorithm repeats $32n^{704}$ independent samples $H_{i}$, and recursively
computes a (biased) estimator $X_{i}$ of $u_{H_{i}}(p/q)$. Let $X$ be the
average of all these estimators $X_{i}$. Next, we use the DNF counting
algorithm in Lemma 4.6 to get an unbiased estimator $Z$ of
$u_{G_{\mathrm{large}}}(q)$. The product $XZ$ is the estimator of $u_{G}(p)$
output by the algorithm.

###  4.2 Bias of the Estimator

We first show that all base cases have bias at most $\delta$, and the
recursive steps are unbiased. Then, we prove by induction that the recursion
keeps the same bound $\delta$ on bias.

We introduce some notations when $E_{\mathrm{large}}$ and $E_{\mathrm{small}}$
are uniquely defined in context. Let $G(p_{1},p_{2})$ be the random subgraph
formed by independently contracting each hyperedge in $E_{\mathrm{large}}$
with probability $1-p_{1}$, and each hyperedge in $E_{\mathrm{small}}$ with
probability $1-p_{2}$. Let $D_{L}$ be the event that in some random
contraction, the contracted hyperedges in $E_{\mathrm{large}}$ do not contract
the whole hypergraph into a singleton.

##### Base cases.

The first base case of $n=O(1)$ outputs the exact value of $u_{G}(p)$ by Lemma
3.1. The second base case of disconnected $G$ is trivial. In the third base
case, the bias is $0-u_{G}(p)\in[-\delta,0]$. Next, we prove that the
algorithm in full revelation case is unbiased.

######  Lemma 4.8.

The algorithm in the full revelation case outputs an unbiased estimator of
$u_{G}(p)$.

###### Proof.

The algorithm first samples $H_{L}\sim G(p,0)\,|\,D_{L}$, then forms $H_{S}$
by deleting all hyperedges in $E_{\mathrm{large}}$ from $H_{L}$, and finally
samples $H\sim H_{S}(p)$. In other words, the subgraph $H_{S}$ is sampled by
either contracting or deleting all large hyperedges, and then $H$ is sampled
from $H_{S}$ by randomly contracting small hyperedges. Let $a$ be the number
of contracted hyperedges in $E_{\mathrm{large}}$. Then, $H_{S}$ is sampled
with probability $p^{a}(1-p)^{\ell-a}/u_{L}$, where $u_{L}=u_{G_{large}}(p)$.

The step estimates $u_{G}(p)/u_{L}$ by $X_{H}$, where $X_{H}=0$ if $H$ is
contracted into a singleton, and $X_{H}=1$ otherwise. We have
$\mathbb{E}[X_{H}|H_{S}]=u_{H_{S}}(p)$ by Lemma 2.2.

$\mathbb{E}[X_{H}]=\mathbb{E}_{H_{S}}[\mathbb{E}[X_{H}|H_{S}]]=\mathbb{E}[u_{H_{S}}(p)]=\sum_{H_{S}}\frac{p^{a}(1-p)^{\ell-a}}{u_{L}}u_{H_{S}}(p)$

The sum is over all $H_{S}$ sampled by either contracting or deleting all
large hyperedges, conditioned on that it is not contracted into singleton by
large hyperedges. The condition can be dropped because when it doesn’t hold we
have $u_{H_{S}}(p)=0$. Then the sum is $u_{G}(p)/u_{L}$.

The algorithm outputs the product $XZ$. $X$ is an average of $X_{H}$; its
expectation is $u_{G}(p)/u_{L}$. $Z$ has expectation $u_{L}$. So the total
expectation is $u_{G}(p)$. ∎

##### Recursive cases.

A random contraction step in the universally small case is unbiased by Lemma
2.2. So, we only need to show this for the partial revelation case. We do this
in two steps. First, we assume that the inductive subproblems in this case
return exact estimators, and show that the resulting estimator after this step
is unbiased. Then, we use this fact to show that if the inductive subproblems
return biased estimators, then the bias does not increase after the partial
revelation step.

Define a _partial revelation step_ to be that of the algorithm in the partial
revelation case, except that we now directly use $u_{G_{\mathrm{large}}}(q)$
times average of $u_{H_{i}}(p/q)$ as the estimator instead of recursively
estimating them.

######  Lemma 4.9.

A partial revelation step is an unbiased estimator of $u_{G}(p)$.

###### Proof.

A partial revelation step can be expressed as $H_{L}\sim G(q,0)\,|\,D_{L}$,
and $H\sim H_{L}(0,q)$. Here, the sampling is viewed as two steps: First, the
algorithm samples a subgraph $H_{L}$ by contracting each large hyperedge with
probability $q$, and rejects samples that are contracted into a singleton. The
probability to keep a sampled $H_{L}$ is $u_{L}=u_{G_{large}}(q)$, so the
probability mass for each $H$ is multiplied by $\frac{1}{u_{L}}$ compared to
the distribution of contracting each large hyperedge with probability $q$.
Second, the algorithm samples $H$ by contracting each small hyperedge with
probability $q$ from $H_{L}$.

Finally, a partial revelation step estimates $u_{G}(p)$ by $u_{L}\cdot
u_{H}(p/q)$. We have

$\displaystyle\mathbb{E}[u_{H}(p/q)]$ $\displaystyle=\mathbb{E}_{H_{L}\sim
G(q,0)|D_{L}}[\mathbb{E}_{H\sim H_{L}(0,q)}u_{H}(p/q)]$
$\displaystyle=\mathbb{E}_{H_{L}\sim G(q,0)}\left[\frac{1}{u_{L}}1[H_{L}\text{
disconnects}]\cdot\mathbb{E}_{H\sim H_{L}(0,q)}u_{H}(p/q)\right]$
$\displaystyle=\frac{1}{u_{L}}\mathbb{E}_{H_{L}\sim G(q,0)}[\mathbb{E}_{H\sim
H_{L}(0,q)}u_{H}(p/q)]$ $\displaystyle=\frac{1}{u_{L}}\mathbb{E}_{H\sim
G(q)}u_{H}(p/q)=\frac{u_{G}(p)}{u_{L}}.$

The third equality drops the indicator function $1[H_{L}\text{ disconnects}]$
because $H_{L}$ being connected implies $u_{H}(p/q)=0$. The last step follows
Lemma 2.2. ∎

We now prove the inductive claim on the bias of the estimator.

######  Lemma 4.10.

The algorithm outputs an estimator with negatively one-sided bias of at most
$\delta$.

###### Proof.

We prove by induction. In the base case of $p^{\lambda}<2^{-3N}$, the output
is 0; so, the bias is negatively one-sided and upper bounded by $u_{G}(p)\leq
n^{2}p^{\lambda}\leq(2^{N})^{2}\cdot 2^{-3N}=2^{-N}=\delta$. The other base
cases are unbiased.

In a random contraction step of universally small case, we take the average
$X=\frac{1}{M}\sum_{i\leq M}X_{i}$. By the inductive hypothesis, each $X_{i}$
satisfies $\mathbb{E}[X_{i}|H_{i}]-u_{H_{i}}(p/q)\in[-\delta,0]$. Then,

$\displaystyle\mathbb{E}[X]-u_{G}(p)$ $\displaystyle=\frac{1}{M}\sum_{i\leq
M}\mathbb{E}[X_{i}]-u_{G}(p)=\frac{1}{M}\sum_{i\leq
M}\mathbb{E}_{H_{i}}[\mathbb{E}[X_{i}|H_{i}]]-\mathbb{E}_{H_{i}}[u_{H_{i}}(p/q)]$
$\displaystyle=\frac{1}{M}\sum_{i\leq
M}\mathbb{E}_{H_{i}}[\mathbb{E}[X_{i}|H_{i}]-u_{H_{i}}(p/q)]\in[-\delta,0].$

In the partial revelation case, $Z$ is the DNF sampling estimator of
$u_{L}=u_{G_{\mathrm{large}}}(q)$, which is unbiased and independent of $X$.
Next, we bound the bias of $X$ compared to $u_{G}(p)/u_{L}$. We take average
$X=\frac{1}{M}\sum_{i\leq M}X_{i}$, and each $X_{i}$ is an estimator for
$u_{H_{i}}(p/q)$ with $\mathbb{E}[X_{i}|H_{i}]-u_{H_{i}}(p/q)\in[-\delta,0]$
by the inductive hypothesis. Note that here $H_{i}$ is sampled from a
different distribution where $\mathbb{E}[u_{H}(p/q)]=u_{G}(p)/u_{L}$ by Lemma
4.9. Then,

$\displaystyle\mathbb{E}[X]-\frac{u_{G}(p)}{u_{L}}$
$\displaystyle=\frac{1}{M}\sum_{i\leq
M}\mathbb{E}[X_{i}]-\frac{u_{G}(p)}{u_{L}}=\frac{1}{M}\sum_{i\leq
M}\mathbb{E}_{H_{i}}[\mathbb{E}[X_{i}|H_{i}]]-\mathbb{E}_{H_{i}}[u_{H_{i}}(p/q)]$
$\displaystyle=\frac{1}{M}\sum_{i\leq
M}\mathbb{E}_{H_{i}}[\mathbb{E}[X_{i}|H_{i}]-u_{H_{i}}(p/q)]\in[-\delta,0].$

After scaling by $\mathbb{E}[Z]=u_{L}\leq 1$, the overall bias of partial
revelation case is

$\mathbb{E}[XZ]-u_{G}(p)=\mathbb{E}[X]\mathbb{E}[Z]-u_{G}(p)=\left(\mathbb{E}[X]-\frac{u_{G}(p)}{u_{L}}\right)\cdot
u_{L}\in[-\delta,0].$

∎

###  4.3 Capped Relative Variance of the Estimator

We first show that the recursive calls do not introduce relative variance.
Then we show that the full revelation base case outputs an unbiased estimator
with bounded relative variance. However, because the base case when
$p^{\lambda}<2^{-3N}$ is biased, we need to control $\delta$-capped relative
variance instead of relative variance. We conclude by bounding capped relative
variance for the whole recursion in Lemma 4.14.

In universally small hypergraphs, we have shown that a random contraction step
has relative variance at most $n^{2}q^{-\lambda}=n^{12}$ in Lemma 3.5.

######  Fact 4.11.

Suppose $X$ is a nonnegative random variable that takes value 0 outside a
subspace $D$, and the measure of $D$ is $u_{D}$. If we do rejection sampling
to sample $X^{\prime}$ that only accepts samples in $D$, then
$\eta[X^{\prime}]\leq u_{D}\cdot\eta[X]$.

###### Proof.

We have

$\mathbb{E}[X]=u_{D}\mathbb{E}[X|D]+(1-u_{D})\mathbb{E}[X|\bar{D}]=u_{D}\mathbb{E}[X|D]=u_{D}\mathbb{E}[X^{\prime}].$

Then, $\mathbb{E}[X^{\prime}]=\mathbb{E}[X]/u_{D}$. By the same argument,
$\mathbb{E}[X^{\prime 2}]=\mathbb{E}[X^{2}]/u_{D}.$ Therefore,

$\eta[X^{\prime}]+1=\frac{\mathbb{E}[X^{\prime
2}]}{\mathbb{E}[X]^{2}}=\frac{\mathbb{E}[X^{2}]/u_{D}}{\mathbb{E}[X]^{2}/u_{D}^{2}}=u_{D}(\eta[X]+1),$

and $\eta[X^{\prime}]\leq u_{D}\cdot\eta[X]$. ∎

######  Lemma 4.12.

In a partial revelation step, each estimator $u_{H_{i}}(p/q)$ has relative
variance at most $n^{4}q^{-\beta}$.

###### Proof.

The samples $H_{i}$ can be viewed as generated by random contraction with
survival probability $q$, but rejected when the contracted hyperedges in
$E_{\mathrm{large}}$ connects. The estimator $u_{H_{i}}(p/q)$ takes value 0
outside the accepting subspace (where $H$ is already contracted), and the
accepting subspace has measure $u_{L}=u_{G_{\mathrm{large}}}(q)$. So by Fact
4.11,

$\eta[u_{H_{i}}(p/q)]\leq u_{L}\cdot\eta_{H\sim G(q)}[u_{H}(p/q)]\leq
n^{2}q^{\lambda_{L}}\cdot n^{2}q^{-\lambda}\leq n^{4}q^{-\beta}.$

Here, we used $u_{L}\leq n^{2}q^{\lambda_{L}}$ by Lemma 3.4, and $\eta_{H\sim
G(q)}[u_{H}(p/q)]\leq n^{2}q^{-\lambda}$ by Lemma 3.5.

∎

######  Lemma 4.13.

The algorithm for full revelation case outputs an unbiased estimator of
relative variance at most $3$.

###### Proof.

Unbiasedness is given by Lemma 4.8. Next, we bound the relative variance.

In the full revelation case, each estimator $X_{i}$ is an indicator function
of $H_{i}$ disconnecting, and the samples $H_{i}$ can be viewed as generated
by random contraction with survival probability $p$, but rejected when the
contracted hyperedges in $E_{\mathrm{large}}$ connect. The estimator $X_{i}$
takes value 0 outside the accepting subspace (where $H$ is already
contracted), and the accepting subspace has measure
$u_{L}=u_{G_{\mathrm{large}}}(p)$. For indicator function $1_{A}$ on any event
$A$, $\eta[1_{A}]<\mathbb{E}[1_{A}^{2}]/(\mathbb{E}[1_{A}]^{2})=1/\Pr[A]$. By
Fact 4.11,

$\eta[X_{i}]\leq u_{L}\cdot\eta_{H\sim G(p)}[1[H_{i}\text{ disconnects}]]\leq
u_{L}/u_{G}(p)\leq n^{2}p^{\lambda_{L}}/p^{\lambda}\leq n^{2}p^{-\beta}.$

Here, we used $u_{L}\leq n^{2}p^{\lambda_{L}}$ and $u_{G}(p)\geq p^{\lambda}$
by Lemma 3.4.

By the definition of full revelation case, $\beta<\lambda/N$, and
$p^{-\beta}\leq p^{-\lambda/N}$. Because we assumed $p^{\lambda}\geq 2^{-3N}$
(otherwise it would be a base case), $p^{-\beta}\leq 2^{3}=8$. So,
$\eta[X_{i}]\leq 8n^{2}$.

$X$ is the average of $8n^{2}$ i.i.d. estimators $X_{i}$. So, $X$ has relative
variance at most $1$ by Fact 2.4. $Z$ is independent of $X$ and has relative
variance at most $1$ by Lemma 4.6. Therefore, the product $XZ$ has relative
variance $\leq\eta[X]\eta[Z]+\eta[X]+\eta[Z]\leq 3$ by Fact 2.6. ∎

######  Lemma 4.14.

The algorithm outputs a (biased) estimator $X$ of $u_{G}(p)$ with capped
relative variance $\eta_{\delta}[X]\leq 3$.

###### Proof.

We prove by induction on the recursion tree. (The induction is valid because
each recursive call decreases $n$, $m$ or $\left\lceil
m\ln\frac{1}{p}\right\rceil$, as argued earlier.) In the base case when
$p^{\lambda}<2^{-3N}$, the algorithm outputs $X=0$, whose $\delta$-capped
relative variance is $0/\delta^{2}=0$. Other base cases are unbiased
estimators of $u_{G}(p)$ with relative variance at most $3$ by Lemmas 3.1 and
4.13.

In the inductive step of random contraction, the first level estimator
$u_{H_{i}}(p/q)$ has relative variance at most $n^{2}q^{-\lambda}-1=n^{12}-1$
by Lemma 3.5. The recursive estimator $X_{i}$ for $u_{H_{i}}(p/q)$ has
negatively one-sided bias of $\leq\delta$ by Lemma 4.10 and
$\eta_{\delta}[X_{i}|H_{i}]\leq 3$ by inductive hypothesis. By Fact 2.5,
(unconditionally) $\eta_{\delta}[X_{i}]\leq 4\cdot n^{12}\cdot(3+1)=16n^{12}$.
The algorithm takes average of $16n^{12}$ estimators, so the overall estimator
has capped relative variance $\leq 1$ by Fact 2.4.

In the inductive step of the partial revelation case, the first level
estimator $u_{H_{i}}(p/q)$ has relative variance $n^{4}q^{-\beta}$ by Lemma
4.12. The recursive estimator $X_{i}$ for $u_{H_{i}}(p/q)$ has negatively one-
sided bias of $\leq\delta$ by Lemma 4.10 and $\eta_{\delta}[X_{i}|H_{i}]\leq
3$ by inductive hypothesis. By Fact 2.5, (unconditionally)
$\eta_{\delta}[X_{i}]\leq 16(n^{4}q^{-\beta}+1)\leq 32n^{704}$. The algorithm
takes average of $32n^{704}$ estimators to obtain $X$, so
$\eta_{\delta}[X]\leq 1$ by Fact 2.4. Finally, the algorithm multiplies $X$ by
$Z$, which is an unbiased estimator of $u_{G_{\mathrm{large}}}(p)$ with
relative variance $\leq 1$ by Lemma 4.6 and is independent of $X$. So, the
product $XZ$ has $\delta$-capped relative variance $\leq 3$ by Fact 2.6. ∎

###  4.4 Running Time

The argument is similar to Section 3.3. We color each recursive call as black
or red. Intuitively, they represent a “success” or “failure” respectively.

For both the universally small and partial revelation cases, if the child
subproblem is a phase node, then the recursive call is marked a success (i.e.,
a black node). This is the only type of success for the universally small
case, which we call type 1 success. For the partial revelation case, we have
an additional situation where we declare type 2 success: when the parameter
$\gamma$ decreases to $0.9\gamma$ and $|\ell-\lambda|\leq 0.1\beta$.

Now, the recursion tree satisfies the following properties:

  1. 1.

Each subproblem makes $n^{O(1)}$ recursive calls. This is clear in the
algorithm description.

  2. 2.

The algorithm reaches the base case after $O(\log n\cdot\log N)$ black
recursive calls (interleaved with red recursive calls). We prove this in Lemma
4.15.

  3. 3.

At each subproblem, the expected number of red recursive calls is $o(1)$. We
prove this later in the section.

Lemma 3.12 shows that these properties give a upper bound of $n^{O(\log
n\cdot\log N)}$ on the number of recursive calls. If we charge the time of DNF
sampling and random contraction to the subproblem on the contracted
hypergraph, then each subproblem spends $O(n^{2}m)$ time outside the recursive
calls, where the bottlenecks are DNF sampling and DNF probability estimation
given by Lemma 4.6. Therefore, the overall expected running time is $m\cdot
n^{O(\log n\cdot\log N)}$.

######  Lemma 4.15.

There can be at most $O(\log n\cdot\log N)$ black recursive calls from root to
a base case.

###### Proof.

There are at most $O(\log n)$ phases from root to a base case because each
phase node decreases $n$ to at most $0.8n$ compared to the last phase node.

Within each phase, $\gamma$ is non-increasing by Lemma 4.7, and each type 2
success decreases $\gamma$ to at most $0.9\gamma$. Note that whenever the type
2 success happens, we are in the case that $|\gamma-\beta|=|\ell-\lambda|\leq
0.1\beta$. Initially, $\beta\leq\lambda$ and the algorithm reaches a base case
when $\beta<\lambda/N$; so, there can be at most $O(\log N)$ recursive calls
with the type 2 success in a branch of the recursion tree within a phase. ∎

Next, we establish property 3 for each case of the recursive step, i.e., that
the expected number of red recursive calls is $o(1)$.

##### Universally small case.

In the universally small case, we can use the same analysis as Algorithm 1.
The algorithm runs $O(n^{12})$ recursive calls, while the failure probability
of each call is $n^{2.7}q^{1.5\lambda}$ by Corollary 3.10. The algorithm
chooses $q^{\lambda}=n^{-10}$ so that their product is $o(1)$.

##### Partial revelation case.

The algorithm runs $O(n^{704})$ recursive calls. We next prove that the
failure probability is at most $n^{2}q^{1.01\beta}=n^{-705}$, so that their
product is $o(1)$.

Consider a computation node $v$ in the partial revelation case. Let $u$ be the
phase ancestor of $v$ (or $u=v$ if $v$ is a phase node), and let $w$ be a
child subproblem called by $v$. Consider the recursive call from $v$ to $w$.
There are two types of success: (1) $w$ is a phase node, i.e. the recursive
call decreases the number of vertices by a constant factor compared to the
phase ancestor $u$, and (2) the parameter $\gamma_{w}$ defined in $w$ is at
most $0.9\gamma$ for $\gamma$ defined in $v$, and we are in the case that
$|\gamma-\beta|\leq 0.1\beta$.

Recall that $\gamma=\ell-\lambda_{L}$ and $\beta=\lambda-\lambda_{L}$, where
$\lambda_{L}$ is the min-cut value in $G_{\mathrm{large}}$, which is equal to
the minimum degree cut value in $G_{\mathrm{large}}$ by Lemma 4.5.

######  Lemma 4.16.

The failure probability in each partial revelation case is at most
$n^{2}q^{1.01\beta}$.

###### Proof.

Let $v$ be the current computation node, $u$ be its phase ancestor (or $u=v$
if $v$ is a phase node), and $w$ be a child subproblem called by $v$. All
parameters and notations are defined in $v$ by default, and we will add
subscripts if they are defined in $u$ or $w$.

We consider three cases. The first case is $\ell>\lambda+0.1\beta$. Then the
probability to not contract any large hyperedge (which is necessary for
failure) is $q^{\ell}/u_{L}\leq
q^{\lambda+0.1\beta}/q^{\lambda_{L}}=q^{1.1\beta}$.

The second case is $\ell<\lambda-0.1\beta$. Failure happens when the following
two independent events both happen:

  1. 1.

No large hyperedge is contracted.

  2. 2.

The random contraction in $G_{small}$ does not decrease the number of vertices
to $\leq 0.8n$.

The first event happens with probability $q^{\ell}/u_{L}\leq
q^{\lambda-0.1\beta-\lambda_{L}}=q^{0.9\beta}$. For the second event, we will
apply Lemma 3.9 on $G_{\mathrm{small}}$. The min-cut value in
$G_{\mathrm{small}}$ is at least $\lambda-\ell$ because the union of the min-
cut in $G_{\mathrm{small}}$ and all hyperedges in $E_{\mathrm{large}}$ is a
cut in $G$. The maximum rank in $G_{\mathrm{small}}$ is at most $0.7n$ by Fact
4.1. So, we can apply Lemma 3.9 with $A=\frac{10}{7},B=\frac{8}{7}$ to bound
the probability of the second event by $n^{2}q^{1.1(\lambda-\ell)}\leq
n^{2}q^{1.1(0.1\beta)}=n^{2}q^{0.11\beta}$. The total failure probability is
upper bounded by $q^{0.9\beta}\cdot n^{2}q^{0.11\beta}=n^{2}q^{1.01\beta}$.

The last case is $\lambda-0.1\beta\leq\ell\leq\lambda+0.1\beta$. We will upper
bound the probability that failure event 1 and the following new failure event
both happen:

  1. 3.

$\gamma_{w}>0.9\gamma$. Hence,

$\ell-\lambda_{L}(w)>0.9(\ell-\lambda_{L})\geq
0.9(\lambda-0.1\beta-\lambda_{L})=0.9(0.9\beta)>0.8\beta.$

This condition becomes $\lambda_{L}(w)<\ell-0.8\beta$ which means that some
vertex $s\in G_{w}$ is incident to less than
$\ell-0.8\beta\leq\lambda-0.7\beta$ hyperedges in $E_{\mathrm{large}}$.

For failure event 1, no large hyperedge gets contracted. This happens with
probability at most $q^{\ell}/u_{L}\leq q^{\ell-\lambda_{L}}$.

We now bound failure event 3 conditioned on failure event 1 occurring. Here,
it suffices to upper bound the probability that some vertex $s\in G_{w}$ is
incident to less than $\lambda-0.7\beta$ hyperedges in $E_{\mathrm{large}}$,
given that no large hyperedge is contracted. The hypergraph under random
contraction is now $G_{\mathrm{small}}$, and this random contraction is
independent of the previous event on $E_{\mathrm{large}}$.

Consider the exponential contraction process on $G_{\mathrm{small}}$. Replace
each hyperedge with two copies (these copies are “half-hyperedges” with
survival probability $\sqrt{q}$ instead of $q$). Assign a head to each
hyperedge, in a way that two copies from a hyperedge have different heads. The
orientation may change during the process after each hyperedge arrives. The
orientation is consistent, which means for any fixed subgraph we always choose
the same orientation. Besides this requirement, the orientation is arbitrary.
We assign a representative to each contracted supervertex during the process.
Originally, each vertex is its own representative. When a hyperedge $e$ is
contracted, the representative of the head of $e$ becomes the representative
of the new contracted supervertex.

Define the critical hyperedges for a supervertex $s$ to be the hyperedges that
contain $s$ as a tail. For the failure event 3 to happen, there exists a
supervertex $\widetilde{s}$ in $w$ that is incident to less than
$\lambda-0.7\beta$ hyperedges in $E_{\mathrm{large}}$. Let $s$ be the
representative of $\widetilde{s}$, so $s$ is a vertex in node $v$. By
extension, we also denote by $\widetilde{s}$ the supervertices that contain
$s$ as a representative throughout the exponential contraction process. (Note
that initially $\widetilde{s}=s$.) Since we do not contract any large
hyperedge, the number of large hyperedges that contain $\widetilde{s}$ can
only increase over time, but by assumption, $\widetilde{s}$ is incident to
less than $\lambda-0.7\beta$ large hyperedges at the end. So throughout the
process, $\widetilde{s}$ is always incident to less than $\lambda-0.7\beta$
hyperedges in $E_{\mathrm{large}}$. Because the degree cut of $\widetilde{s}$
has value at least $\lambda$, $\widetilde{s}$ is always incident to at least
$0.7\beta$ hyperedges in $E_{\mathrm{small}}$. Then, it always has $0.7\beta$
critical (half-)hyperedges after duplication.

By Lemma 3.7, the probability that such a vertex $s$ will survive as a
representative until time $\ln\frac{1}{\sqrt{q}}$ is at most
$(\sqrt{q})^{0.7\beta}=q^{0.35\beta}$. By a union bound, the probability of
failure event 3 (conditioned on failure event 1) is at most $nq^{0.35\beta}$.
The total failure probability is $q^{0.9\beta}\cdot
nq^{0.35\beta}=nq^{1.25\beta}$. ∎

##  5 Conclusion

In this paper, we initiated the study of unreliability in hypergraphs and
provided quasi-polynomial time approximation schemes for the problem. The
immediate open question is whether there is a PTAS (or even FPTAS) for this
problem. More generally, we hope that our work will inspire further
exploration of the rich space of reliability problems in hypergraphs. For
instance, a natural complementary question to network unreliability is that of
network reliability, i.e., estimating the probability that a network stays
connected under independent random failures of the (hyper)edges. For graphs,
there are PTAS for this problem using very a different set of techniques from
network unreliability [GJ19, GH20, CGZZ23]; the corresponding problem in
hypergraphs remains open.

## Acknowledgments

RC and DP were supported in part by NSF grants CCF-1750140 (CAREER),
CCF-1955703, and CCF-2329230. This research was done at the Simons Institute,
UC Berkeley in Fall 2023 when RC was a Visiting Graduate Student, JL was a
Simons Fellow, and DP was a Visiting Scientist in the semester program on Data
Structures and Optimization for Fast Algorithms at the institute. DP also
wishes to acknowledge the support of Google Research, where he was a (part-
time) visiting faculty researcher at the time of this research. RC and DP
would also like to thank William He and Davidson Zhu for discussions at an
early stage of this research.

## References

  * [AFW95] Noga Alon, Alan M. Frieze, and Dominic Welsh.  Polynomial time randomized approximation schemes for tutte-gröthendieck invariants: The dense case.  Random Struct. Algorithms, 6(4):459–478, 1995.
  * [BGHS23] Christian Bick, Elizabeth Gross, Heather A. Harrington, and Michael T. Schaub.  What are higher-order networks?  SIAM Rev., 65(3):686–731, 2023.
  * [CGZZ23] Xiaoyu Chen, Heng Guo, Xinyuan Zhang, and Zongrui Zou.  Near-linear time samplers for matroid independent sets with applications.  arXiv preprint arXiv:2308.09683, August 2023.
  * [Cha16] Sanjay Kumar Chaturvedi.  Network reliability: measures and evaluation.  John Wiley & Sons, 2016.
  * [CHLP24] Ruoxu Cen, William He, Jason Li, and Debmalya Panigrahi.  Beyond the quadratic time barrier for network unreliability.  In 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1542–1567, 2024.
  * [CKL+22] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022.
  * [Col87] Charles J Colbourn.  The combinatorics of network reliability.  Oxford University Press, Inc., 1987.
  * [CQ21] Chandra Chekuri and Kent Quanrud.  Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity.  In 48th International Colloquium on Automata, Languages, and Programming (ICALP), pages 50:1–50:20, 2021.
  * [Cun83] William H Cunningham.  Decomposition of submodular functions.  Combinatorica, 3(1):53–68, 1983.
  * [CX18] Chandra Chekuri and Chao Xu.  Minimum cuts and sparsification in hypergraphs.  SIAM Journal on Computing, 47(6):2118–2156, 2018.
  * [DKL76] E.A. Dinitz, A.V. Karzanov, and M.V. Lomonosov.  On the structure of a family of minimal weighted cuts in a graph.  Studies in Discrete Optimization (in Russian), (ed. A.A. Fridman), Nauka, Moscow, page 290–306, 1976.
  * [GH20] Heng Guo and Kun He.  Tight bounds for popping algorithms.  Random Structures & Algorithms, 57(2):371–392, 2020.
  * [GJ19] Heng Guo and Mark Jerrum.  A polynomial-time approximation algorithm for all-terminal network reliability.  SIAM Journal on Computing, 48(3):964–978, 2019.
  * [GKP17] Mohsen Ghaffari, David R Karger, and Debmalya Panigrahi.  Random contractions and sampling for hypergraph and hedge connectivity.  In 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1101–1114, 2017.
  * [GZCN09] Gourab Ghoshal, Vinko Zlatic, Guido Caldarelli, and M. E. J. Newman.  Random hypergraphs and their applications.  Phys. Rev. E, 79:066118, Jun 2009.
  * [HS18] David G. Harris and Aravind Srinivasan.  Improved bounds and algorithms for graph cuts and network reliability.  Random Structures & Algorithms, 52(1):74–135, 2018.
  * [Kar93] David R. Karger.  Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm.  In Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 21–30, 1993.
  * [Kar99] David R. Karger.  A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem.  SIAM Journal on Computing, 29(2):492–514, 1999.
  * [Kar16] David R. Karger.  A fast and simple unbiased estimator for network (un)reliability.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 635–644, 2016.
  * [Kar17] David R. Karger.  Faster (and still pretty simple) unbiased estimators for network (un)reliability.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 755–766, 2017.
  * [Kar20] David R. Karger.  A phase transition and a quadratic time unbiased estimator for network reliability.  In 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), page 485–495, 2020.
  * [KK15] Dmitry Kogan and Robert Krauthgamer.  Sketching cuts in graphs and hypergraphs.  In 2015 Conference on Innovations in Theoretical Computer Science (ITCS), pages 367–376, 2015.
  * [KLM89] Richard M Karp, Michael Luby, and Neal Madras.  Monte-carlo approximation algorithms for enumeration problems.  Journal of algorithms, 10(3):429–448, 1989.
  * [Val79] Leslie G. Valiant.  The complexity of enumeration and reliability problems.  SIAM Journal on Computing, 8(3):410–421, 1979.

##  Appendix A Missing Proofs from Section 2

##### Proofs on capped relative variance.

We first state the following standard facts about relative variance. The also
serve as special cases of Fact 2.5 and Lemma 2.7.

######  Fact A.1 ([Kar17]).

Suppose $Y$ is an unbiased estimator of $x$ with relative variance $\eta_{1}$,
and given any fixed value of $Y$, $Z$ is an unbiased estimator of $Y$ with
relative variance $\eta_{2}$. Then $Z$ is an unbiased estimator of $x$ with
relative variance $(\eta_{1}+1)(\eta_{2}+1)-1$.

######  Lemma A.2 ([Kar17]).

Fix $\varepsilon,\delta\in(0,1)$. For a random variable $X$ with relative
variance $\eta[X]$, the median of $O(\log\frac{1}{\delta})$ averages of
$O(\frac{\eta[X]}{\varepsilon^{2}})$ independent samples of $X$ is a
$(1\pm\varepsilon)$-approximation of $\mathbb{E}[X]$ with probability at least
$1-\delta$.

Recall that all random variables discussed in the paper are non-negative. This
will be implicitly used in the following proofs.

###### Proof of Fact 2.4.

For i.i.d. samples, the denominator $\max\\{(\mathbb{E}[X])^{2},\delta^{2}\\}$
is identical, while the numerator $\mathrm{Var}[X]$ is divided by $M$ after
taking average. So, the capped relative variance is divided by $M$. ∎

###### Proof of Fact 2.5.

The special case is given by Fact A.1. Next, we consider general case
$\delta>0$. We start with

$\mu=\mathbb{E}[Z]=\mathbb{E}_{Y}[\mathbb{E}[Z|Y]]\in[\mathbb{E}[Y-\delta],\mathbb{E}[Y]]=[x-\delta,x].$

This implies $\mu+\delta\geq x$ and $\max\\{\mu,\delta\\}\geq\frac{1}{2}x$. We
can bound $\eta_{\delta}[Z]$ by

$\eta_{\delta}[Z]=\frac{\mathbb{E}[Z^{2}]-\mu^{2}}{\max\\{\mu^{2},\delta^{2}\\}}\leq\frac{\mathbb{E}[Z^{2}]}{\max\\{\frac{1}{4}x^{2},\delta^{2}\\}}.$

Notice that

$\mathbb{E}[Z^{2}]=\mathbb{E}_{Y}[\mathbb{E}[Z^{2}|Y]]=\mathbb{E}_{Y}\left[\max\\{Y^{2},\delta^{2}\\}\cdot\frac{\mathbb{E}[Z^{2}|Y]}{\max\\{Y^{2},\delta^{2}\\}}\right]\leq\max\\{\mathbb{E}[Y^{2}],\delta^{2}\\}\cdot\max_{Y}\frac{\mathbb{E}[Z^{2}|Y]}{\max\\{Y^{2},\delta^{2}\\}}.$

Thus,

$\eta_{\delta}[Z]\leq\frac{\max\\{\mathbb{E}[Y^{2}],\delta^{2}\\}}{\max\\{\frac{1}{4}x^{2},\delta^{2}\\}}\cdot\max_{Y}\frac{\mathbb{E}[Z^{2}|Y]}{\max\\{Y^{2},\delta^{2}\\}}\leq\max\left\\{\frac{4\mathbb{E}[Y^{2}]}{x^{2}},1\right\\}\cdot\max_{Y}\frac{\mathbb{E}[Z^{2}|Y]}{\max\\{Y^{2},\delta^{2}\\}}.$

The first term is upper bounded by $4(\eta[Y]+1)$ because
$\eta[Y]+1=\frac{\mathbb{E}[Y^{2}]}{x^{2}}$ by definition. The second term is
upper bounded by $h+1$ because for all fixed $Y$,

$h\geq\eta_{\delta}[Z|Y]=\frac{\mathbb{E}[Z^{2}|Y]-(\mathbb{E}[Z|Y])^{2}}{\max\\{\mathbb{E}[Z|Y],\delta\\}^{2}}\geq\frac{\mathbb{E}[Z^{2}|Y]-Y^{2}}{\max\\{Y,\delta\\}^{2}}\geq\frac{\mathbb{E}[Z^{2}|Y]}{\max\\{Y,\delta\\}^{2}}-1.$

In conclusion $\eta_{\delta}[Z]\leq 4\cdot(\eta[Y]+1)\cdot(h+1)$. ∎

###### Proof of Fact 2.6.

Under the assumptions,

$\displaystyle\max\\{(\mathbb{E}[X])^{2},\delta^{2}\\}\cdot\max\\{(\mathbb{E}[Z])^{2},\delta^{2}\\}$
$\displaystyle=\max\\{(\mathbb{E}[X]\mathbb{E}[Z])^{2},(\mathbb{E}[X])^{2}\delta^{2},(\mathbb{E}[Z])^{2}\delta^{2},\delta^{4}\\}$
$\displaystyle\leq\max\\{(\mathbb{E}[X]\mathbb{E}[Z])^{2},\delta^{2}\\}.$

Therefore,

$\displaystyle\eta_{\delta}[XZ]$
$\displaystyle=\frac{\mathrm{Var}[XZ]}{\max\\{(\mathbb{E}[XZ])^{2},\delta^{2}\\}}=\frac{\mathrm{Var}[X]\mathrm{Var}[Z]+\mathrm{Var}[X](\mathbb{E}[Z])^{2}+\mathrm{Var}[Z](\mathbb{E}[X])^{2}}{\max\\{(\mathbb{E}[X])^{2}(\mathbb{E}[Z])^{2},\delta^{2}\\}}$
$\displaystyle\leq\frac{\mathrm{Var}[X]\mathrm{Var}[Z]+\mathrm{Var}[X](\mathbb{E}[Z])^{2}+\mathrm{Var}[Z](\mathbb{E}[X])^{2}}{\max\\{(\mathbb{E}[X])^{2},\delta^{2}\\}\cdot\max\\{(\mathbb{E}[Z])^{2},\delta^{2}\\}}$
$\displaystyle\leq\eta_{\delta}[X]\eta_{\delta}[Z]+\eta_{\delta}[X]+\eta_{\delta}[Z].\qed$

###### Proof of Lemma 2.7.

If $\mathbb{E}[X]\geq\delta$, then $\eta_{\delta}[X]=\eta[X]$ and the lemma
follows Lemma A.2.

If $\mathbb{E}[X]<\delta$, $\eta_{\delta}[X]=\mathrm{Var}[X]/\delta^{2}$.
Consider $X^{\prime}=X+\delta$.

$\eta[X^{\prime}]=\frac{\mathbb{E}[X^{\prime
2}]}{\mathbb{E}[X^{\prime}]^{2}}-1=\frac{\mathbb{E}[X^{2}]+2\delta\mathbb{E}[X]+\delta^{2}}{\mathbb{E}[X]^{2}+2\delta\mathbb{E}[X]+\delta^{2}}-1\leq\frac{\mathrm{Var}[X]}{\delta^{2}}=\eta_{\delta}[X]$

So we can apply Lemma A.2 to get a $(1+\varepsilon)$-approximation of
$X+\delta$, which is a $(1+\varepsilon,\delta)$-approximation of $X$ after
subtracting $\delta$. ∎

###### Proof of Fact 2.8.

Suppose $X=\sum_{i\leq k}\alpha_{i}X_{i}$ and $\mathbb{E}[X_{i}]=\mu_{i}$.
Then

$\displaystyle\eta[X]$
$\displaystyle=\frac{\mathbb{E}[(\sum_{i}\alpha_{i}X_{i})^{2}]}{(\sum_{i}\alpha_{i}\mu_{i})^{2}}-1=\frac{\sum_{i,j}\alpha_{i}\alpha_{j}\mathbb{E}[X_{i}X_{j}]}{\sum_{i,j}\alpha_{i}\alpha_{j}\mu_{i}\mu_{j}}-1$
$\displaystyle=\frac{\sum_{i}\alpha_{i}^{2}\mathbb{E}[X_{i}^{2}]+\sum_{i\neq
j}\alpha_{i}\alpha_{j}\mathbb{E}[X_{i}]\mathbb{E}[X_{j}]}{\sum_{i}\alpha_{i}^{2}\mu_{i}^{2}+\sum_{i\neq
j}\alpha_{i}\alpha_{j}\mu_{i}\mu_{j}}-1$
$\displaystyle=\frac{\sum_{i}\alpha_{i}^{2}(\mathbb{E}[X_{i}^{2}]-\mu_{i}^{2})}{\sum_{i}\alpha_{i}^{2}\mu_{i}^{2}+\sum_{i\neq
j}\alpha_{i}\alpha_{j}\mu_{i}\mu_{j}}$
$\displaystyle\leq\frac{\sum_{i}\alpha_{i}^{2}(\mathbb{E}[X_{i}^{2}]-\mu_{i}^{2})}{\sum_{i}\alpha_{i}^{2}\mu_{i}^{2}}$
$\displaystyle\leq\max_{i}\frac{\mathbb{E}[X_{i}^{2}]-\mu_{i}^{2}}{\mu_{i}^{2}}=\max_{i}\eta[X_{i}]$

∎

###### Proof of Fact 2.9.

$\eta[X]=\frac{\mathbb{E}[X^{2}]}{(\mathbb{E}[X])^{2}}-1\leq\frac{\mathbb{E}[X\cdot
M]}{(\mathbb{E}[X])^{2}}-1=\frac{\mathbb{E}[X]\cdot
M}{(\mathbb{E}[X])^{2}}-1=\frac{M}{\mathbb{E}[X]}-1$

∎

###### Proof of Lemma 2.13.

The estimator $X$ follows a binomial distribution of parameter $p_{D}$, so
$\mathbb{E}[X]=p_{D}$ and $\mathrm{Var}[X]=p_{D}(1-p_{D})\leq p_{D}$. It
follows that
$\eta[X]=\frac{\mathrm{Var}[X]}{\mathbb{E}[X]^{2}}\leq\frac{1}{p_{D}}$. For
capped relative variance, when $p_{D}\geq\delta$,
$\eta_{\delta}[X]=\frac{\mathrm{Var}[X]}{p_{D}^{2}}\leq\frac{1}{p_{D}}$; when
$p_{D}<\delta$,
$\eta_{\delta}[X]=\frac{\mathrm{Var}[X]}{\delta^{2}}\leq\frac{p_{D}}{\delta^{2}}\leq\frac{1}{\delta}$.
∎

We prove Lemmas 2.16 and 2.17 together:

###### Proof of Lemmas 2.16 and 2.17.

For each clause $C_{i}$, suppose it has $a_{i}$ positive literals and $b_{i}$
negative literals. Then the probability that $C_{i}$ is satisfied is
$p^{a_{i}}(1-p)^{b_{i}}$. Denote this as $u_{i}$.

We first give a sampling algorithm as follows. Pick a clause $C_{i}$ with
probability $u_{i}/U$, where $U=\sum_{C_{j}\in F}u_{j}$ is a normalizer. Set
all variables in $C_{i}$ to satisfy $C_{i}$, i.e., variables in positive
literals are True and variables in negative literals are False. Set other
variables randomly, such that each variable is True with probability $p$
independently. Denote the Boolean vector of variable values by $x$. The
algorithm accepts a sample with probability $\frac{1}{f(x)}$ and rejects it
with probability $1-\frac{1}{f(x)}$, where $f(x)$ the number of clauses
satisfied by the sample values $x$. Note that $x$ at least satisfies $C_{i}$;
so $f(x)\geq 1$, i.e. the algorithm only draw samples that satisfy $F$.

Consider any $x$ that satisfies $F$. Suppose there are $a_{x}$ Trues and
$b_{x}$ Falses in $x$. Let the clauses satisfied by $x$ be
$C_{i_{1}},C_{i_{2}},\ldots,C_{i_{f(x)}}$. In the algorithm, $x$ can be drawn
in $f(x)$ different ways when we pick each $C_{i_{k}}$. The total probability
to sample $x$ is

$\sum_{k=1}^{f(x)}\frac{u_{i_{k}}}{U}\cdot
p^{a_{x}-a_{i_{k}}}(1-p)^{b_{x}-b_{i_{k}}}=\sum_{k=1}^{f(x)}\frac{p^{a_{i_{k}}}(1-p)^{b_{i_{k}}}}{U}\cdot
p^{a_{x}-a_{i_{k}}}(1-p)^{b_{x}-b_{i_{k}}}=\frac{f(x)p^{a_{x}}(1-p)^{b_{x}}}{U}$

We accept $x$ with probability $\frac{1}{f(x)}$, so the probability to sample
and accept $x$ is $p^{a_{x}}(1-p)^{b_{x}}/U$. The total the probability that
the algorithm accepts a sample is

$\sum_{x:f(x)\geq 1}\frac{p^{a_{x}}(1-p)^{b_{x}}}{U}=\frac{u_{F}(p)}{U}$

Therefore, among the accepted samples, $x$ is sampled with probability
$p^{a_{x}}(1-p)^{b_{x}}/u_{F}(p)$, which is the desired distribution.

The algorithm takes $O(N)$ time to pick $C_{i}$ and sample $x$. Then, the
algorithm takes $O(NM)$ time to count $f(x)$ by checking whether each clause
is satisfied by $x$. In addition, the algorithm accepts a sample with
probability $\frac{1}{f(x)}\geq\frac{1}{M}$. So, we expect to accept a sample
in $O(M)$ trials, and the expected running time is $O(NM^{2})$ in total.

Next, we show that this algorithm can be used to estimate $u_{F}(p)$. We
proved that the algorithm accepts a sample with probability $u_{F}(p)/U$,
while $U$ can be directly computed. So, we can define an estimator $X$ by
$X=U$ when the algorithm accepts a sample, and $X=0$ when rejects. Then
$\mathbb{E}[X]=u_{F}(p),\mathrm{Var}[X]<\mathbb{E}[X^{2}]=u_{F}(p)\cdot U$.
Notice that $u_{F}(p)\geq u_{j}$ for any $j$. So $U=\sum_{C_{j}\in F}u_{j}\leq
M\cdot u_{F}(p)$, and
$\eta[X]=\frac{\mathrm{Var}[X]}{\mathbb{E}[X]^{2}}\leq\frac{U}{u_{F}(p)}\leq
M$. By taking the average of $M$ estimators, we get an unbiased estimator of
relative variance at most $1$. The running time is again $O(NM^{2})$. ∎