Approximating the Permanent with Deep Rejection Sampling
Authors: Juha Harviainen
Antti Röyskö
Mikko Koivisto
Venue: NeurIPS 2021 Poster (2021)
Keywords: approximation scheme
matrix permanent
practice
rejection sampling

Abstract: We present a randomized approximation scheme for the permanent of a matrix with nonnegative entries. Our scheme extends a recursive rejection sampling method of Huber and Law (SODA 2008) by replacing the permanent upper bound with a linear combination of the subproblem bounds at a moderately large depth of the recursion tree. This method, we call deep rejection sampling, is empirically shown to outperform the basic, depth-zero variant, as well as a related method by Kuck et al. (NeurIPS 2019).  We analyze the expected running time of the scheme on random $(0, 1)$-matrices where each entry is independently $1$ with probability $p$. Our bound is superior to a previous one for $p$ less than $1/5$, matching another bound that was only known to hold when every row and column has density exactly $p$.

Approximating the Permanent with Deep Rejection Sampling
Juha Harviainen University of Helsinki juha. www.haaiiiinneeeessiiiii.... fi
Antti Röyskö ETH Zürich
aroeyskoe@ethz.ch ch
Mikko Koivisto
University of Helsinki mikko koivistooheelsnnii..
Abstract
We present randomized approximation scheme for the permanent of matrix with nonnegative entries. Our scheme extends a recursive rejection sampling method of Huber and Law (SODA 2008) by replacing the upper bound for the permanent with a linear combination the subproblem bounds at a moderately large depth of the recursion tree. This method, we call deep rejection sampling, is empirically shown to outperform the basic, depth-zero variant, as well as a related method by Kuck et al. (NeurIPS 2019). We analyze the expected running time of the scheme on random (0. 1) -matrccs where each entry is independently 1 with probability p. Our bound superior a previous one for p less than 1/5, matching another bound that was known to hold when every row and column has density exactly
Introduction
The permanent of an n x n matrix A (asz) is defined as
perA: == Ea(a), with a(o) = II (io(1)
(1)
where the sum is over permutations a on 21. n). The permanent appears in numerous applications in various domains, including communication theory [31]. multi-target tracking [37, 23 permutation tests on truncated data [8], and the dimer covering problem 2 Bipartite graphs have the well-known property that the permanent of an adjancency matrix of such graph is equal to the number its perfect matchings.
Finding the permanent is notorious computational problem. The fastest known exact algorithms run in time O(2"n) 22 [5), and presumably no polynomial-tim algorithm exists, the problem is #a-hard [38] If negative entries are allowed, just deciding the sign of the permanent is equally hard (2I. For matrices with nonnegative entries, a fully polynomial-timg -ime randomized approximation scheme, FPRAS, was discovered two decades ago [1]] and later the time requirement was lowered to Onn log" n) [.. However, the high degree of the polynomial and a large constant factor render the scheme infeasible in practice [25]. Other, potentially more practical Godsil Godsil-Gutmanl Gutman [16] type estimators obtain high-confidence low-error approximations with (/2))2) evaluations of the deter- minant of an appropriate random n x n matrix over the reals [16] 22 complex numbers [22), or quaternions [9]. with equal to 3, and 3/2, respectively. These schemes might be feasible up to
around n = 50, but clearly not for n 2 100.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

From a practical viewpoint, however, (asymptotic) worst- case bounds are only of secondary interest: it would suffice that an algorithm outputs an estimate that, with high probability, guaranteed to be within small relative error of the exact value-ne no good upper bound for the running time is required a priori; it is typically satisfactory that the algorithm runs fast on the instances one encounters in practice. The artificial intelligence research community, in particular, has found this paradigm attractive for problems in various domains, including probabilistic inference 71 weighted model counting [12 [1I, network reliability [26), and counting linear extensions [35]
For approximating the permanent, this paradigm was recently followed by Kuck et al. 23 Their AdaPart method is based on rejection sampling of permutations proportionally to the weight a (o) given in (. It repeatedly draws a uniformly distributed number between zero and an upper bound U(A) 2 perAA and checks whether the number maps to some permutation Ø. The check is performed iteratively, by sampling one row-column pair at a time, rejecting the trial as soon as the drawn number is known to fall outside the set spanned by the permutations, whose measure is per.A. The expected running time of the method is linear in the ratio (AA)/perA, motivating the use of a bound that is as tight possible. Critically, the bound U is required to "nest" (a technical monotonicity property we detail in Section 2 constraining the design space. This basic strategy of AdaPart stems from earlier methods by Huber and Law [17 19], which aimed at improved polynomial worst-case running time bounds for dense matrices. The key difference is that AdaPart dynamically chooses the next column to be paired with some row, whereas the method of Huber and Law proceeds in the static increasing order of columns. Thanks to this flexibility, AdaPart can take advantage of a tighter upper bound for the permanent that would not nest with respect to the static recursive partitioning.
In this paper, we present a way to boost the said rejection samplers. Conceptually, the idea simple: we replace the upper bound U(4) by linear combination of the bounds for all submatrices that remain after removing the first columns and the associated any rows. Here the depth d is a parameter specified by the user, the larger its value, the better the bound, but also the larger the time requirement of computing the bound. This can be viewed as an instantiation a generic method we call deep rejection sampling or DeepAR (deep acceptance-rrjection)) Our main observation is that for the permanent the computations can be carried out in time that scales, roughly, as 2d, whereas straightforward approach would scale n", being infeasible for all but very small d. We demonstrate empirically that "deep bounds", with around 20, are computationally fcasible and can yield wnders-offmaanitude savings in running time as compared to the basic depth-zero bounds.
We also study analytically how the parameter d affects the ratio of the upper bound and the permanent. Following series of previous works (22 13 [4], we consider random (0, 1) -matricess where each entry takes value 1 with probability p. independently of the rest. We give a bound that holds with high probability and, when specialized to d = 0 and viewed as a function of and p, closely resembles Huber's [17] worst-case bound that holds whenever every row- and column-sum is exuctly pn. We will compare the resulting time complexity bound of our approximation scheme to bounds previously proven for Godsil-Gutman type estimators [22] [3] and some simpler Monte Carlo schemes [27] [4]] and argue, in the spirit of Frieze and Jerrum B Sec. 6], that ours is currently the fastest practical and "trustworthy" scheme for random matrices.
2 Approximate weighted counting with rejection sampling
We begin with generic method for exact sampling and approximate weighted counting called self-reducible acceptance- rejection. We also review the instantiations of the method to sampling weighted permutations due to Huber and Law [7 19 and Kuck et al. (23]
2.1 Self-reducible rejection sampling
In general terms, we consider the following problem of approximate weighted counting. Given set Ω each element x E Ω associated with nonnegative weight w(r), and numbers c, 8 >> O, we wish to compute an (e, 8) approxxiiatnonn of ((2)) ;= Even w(x). that is, a random variable that with probability at least 1 - ò is within a factor of 1 + e of the sum.
The self reducible
cereptance-reecction method 17 solves the problem assuming access
(i) a partition free of Ω that is, a rooted tree where the root is Q each leaf is a singleton set, and the children of each node partition the node into two or more nonempty subsets;

---

iii an upper bound that nests over the partition tree, that is, function u that associates each node a number u(S) that equals w(x) when S {z), and is at least Ei= u(S)) when the children of S are S1, S2.......
The main idea to estimate the ratio of w((2)) to the upper bound u(2) by drawing uniform random numbers from the range (0, u(S)) and accept a draw if it lands in an interval of length w(x) spanned by some z E Qt and reject otherwise. The empirical acceptance rate is known [10] to yield an (e, -approximation of the ratio as as the number of accepted draws is at least *h(e,) 8) := + 2.88 +e) E) (2/2) The following function implements this scheme by calling subroutine SAMPLE( u), which makes independent draw, returning if accepted, and 0 otherwise. (Huber's [8] Gamma Bernoulli acceptance scheme, GBAS, reduces the required number of draws to around one third for practical values of and ó; see Supplement A.1.)
Function ESTIMATE(Q e,
E1 A: + TTb(e, 0)], 0, +
E2 Repeat & < t ++++1 1, +- 8 + SAMPLE(S2, u) until s
E2 Return (I2) k/t
The partition tree and the nesting property are vital for implementing the sampling subroutine, enabling sequential random zooming from the ground set Ω to a single element of it.
Function SAMPLE(S, u)
S1 [|| then return 1; else partition S into S .,,...,,, Sn
S2 p(i) < u(S:)/u(S) for i 1, n. p(0) - p(1)
$3 Draw i ~ p(i)
S4 If i > then return SAMPLE(S;; (S;, u): else return 0
2.2 Application to approximating the permanent
Huber and Law 17 19 instantiate the method to approximating the permanent of an matrix A with nonnegative entries by letting be the set of all permutations on N == (1,2,..., nn and letting the weight function equal a. The recursive partitioning is obtained by simply branching on the row o (o) for each column j = 1,2,..., n increasing order. The bound и derived from an appropriate upper bound (AA) 2 perA as follows. Let S be the bijection between rows and columns J/ and denote the corresponding column for the row i by (i). We get the upper bound at S by multiplying the upper bound for the permanent of the remaining matrix by the product of the already picked entries:
permutations that fix
u(S) = II (20)0) (Arz). &E!
Here 7 and J are the complement sets of 7 and J in relation N, and indexing by subsets specifies a submatrix in an obvious manner. Note that u(2) = U(A) and u(fa)) = a(o), provided that we let U(A) 1 when vanishes, i.e., has zero rows and columns.
Various upper bound for the permanent are known. Let A; denote the ith row vector of A, and let |A,] denote the sum of its entries. For the permanent of (0, 1) -matrix, Mine conjectured [4] and Brègman proved [5] the Minc-Brègma bound
MB (A)
II r(AI)) with 700) 0 and ((k) (kt) for k 1.2.....
An extension to arbitrary nonnegative weights is credited to Brouwer in Schrijver's 's work 30 and published in corrected form by Soules [33] cf. Footnote 4]. Letting aj 2 a 2 ... 2 ai be the entries of A, arranged into nonincreasing order, the Brouwer-Schine Schrijver bound is given by
7
n
U BS (A) = I1
a [T(()) - 7(k 1)]
1=
3

---

One can verify that for a (0, -amttix the bound equals the Minc Brèegan bound.
Since the Minc-Brègman bound does yield, through (2), nesting upper bound the recursive column-wise partitioning, Huber and Law [9] introduced a somewhat looser upper bound, which has that desired property:
h1 ((A)))
h(r) = { r (Ir))/2ee 1 otherwise.
U HI (A)
II
(3)
1 (e - 1)r,
We will refer this as the Huber-Law bound.
In order to employ the tighter Scoriver-ccrrjver bound, Kuck al. [23 replaced the static column- minimize the the set of permutations that fix
wise partitioning by dynamic partitioning, where the next column is selected sum of the bounds of the resulting parts. More formally, bijection between rows and columns J, then S is partitioned according to column j E J into sets
Siy = fo E o =)) E
such that Eisj u(S.t)) is minimized. Furthermore, if the smallest exceeds the bound uSS). then the partition is refined by replacing some set Sig by its minimizing partition; this is repeated until the nesting condition is met. Kuck et al. report that the initial minimizing partition of S was always sufficient in their experiments; this is vital for computational efficiency.
Example It was left open whether the Brouwer-Schrijee bound is guaranteed nest over the dynamic partitioning. The following matrix C is a counterexample, showing the answer is negative:
1
1
0
C
1
1
0
0 1/
Indeed, have (C) (4!) 4V6, but for any column j. the bounds of the three
submatrices that remain after removing column j and row i with nonzero entry at (4.j) sum up to + (31)2/3(21)1/2 = (481/3 + 362 2 > 2/2(48. 36))/6 = 4v6. Here we used the fact that the inequality (a + 6)/2 2 va b holds with equality only if a = b.
3 Deep rejection sampling
This section gives recipe for boosting self-reducible acceptance-rejection. We formulate our method, DeepAR, first in general terms in Section 3.1 and then instantiate to the permanent in Section 3.2
3.1 Deep bounds
Consider fixed partition tree of Ω. Denote by P(S) the set of children of node S C Ω. For d 2 0, define the set of depth-d descendants of S, denoted by Pa(S), recursively by
Po(S) = (S), Pat1(S) = U Pa(R).
REP(S)
We obtain the node set of the partition tree as P= Un2o (S.).
:=
Suppose u is an upper bound over P.. Define the depth-d upper bound at S E Px((2) as ua(S) =
uSS) if > d, and otherwise as
(S(
Σ
u(R).
REPa-N(S)
In words, the depth-d upper bound node S of the partition tree is obtained by summing up the upper bounds at the nodes in the subtree rooted at S that are at depth in the whole partition tree. If nests, then does ua and ua(l)) decreases from u(?) to w({)) d increases; the former is obtained at = 0 and the latter at any sufficiently large d (logarithmic in [2t] suffices).
Our idea is to simply replace the basic bound by the depth-d upper bound in the rejection sampling routine SAMPLEE(S, u). This directly increases the acceptance rate by a factor of (I))) potentially yielding large computational saving for larger d.

---

{
{(x) x EQ]
(2)
{f) x re
Pa(
(a) Basic, depth-zero
(b) Deep. depth-d
Figure Schematic illustration of basic and deep self-reducible acceptance-rrjection. Accepted draws are shown as red thicker arrows, rejected draws as grey arrows.
The main obstacle to efficient implementation of this idea is the complexity of evaluating US(SS at given For each node S at depth at most d, we need to sum up the bounds u( R) at the descendants R of S at depth d: straightforward computing is demanding due to the large number of nodes R. while precomputing, simultaneously for all S, demanding already due the number of nodes S.
One observation comes to rescue: it suffices that we can sample nodes R at depth d in the partition tree proportionally to the respective upper bounds. Put otherwise, we add the following line the beginning of the SAMPLE function, completing the description of DeepAR:
SO S 52 then draw R E Pa((2) with probability u u(R)/uu un (Q., return SAMPLE (R, u)
In effect, sampling begins directly at depth d, skipping d recursive steps of the original routine (Fig. I This allows us to employ, in principle, any algorithm to sample at depth d, potentially making use of problem structure other than what is represented by the partition tree. It depends the problem hand, more precisely on the upper bound u, how efficient algorithms are available. We next see that the upper bounds for the permanent given in Section admit relatively efficient algorithm.
3.2 Deep bounds for the permanent
We now implement step SO for an upper bound U for the permanent. The key property we need is that (A) factorizes into a product of n terms, the ith term only depending on A,, the ith of A; all the bounds reviewed in Section 2.2 have this property. We let ((A,) denote the ith term.
Consider fixed set of columns J C N. Denote 7/ 7(A,)) and 7 Ili Y for short. By summing over all row subsets C N of size d == [J]. we get
Ua(A)
A Σ per Ars per &
Σ Arr U(Ars) Σ per 17 YN Σ perBIs
where B (bij) is the rectangular matrix with the index set N x J and entries big == azj 7 The sum E, B,, equals the permanent of B given by per == Σ, [[eeJ br())= where the sum over all injections from J to N. Thus, in step SO, row subset / is drawn with probability pr.perrr Note that drawing the injection T is unnecessary, since it only affects the bound U(A,)) through the selected rows r(J).
It remains to show how to generate random I without explicitly considering all the (*) sets. To this end, we employ an algorithm for the permanent of rectangular matrices due to Björklund al. Write gi (K) Ber with 21,2,...,. For i > 0 and nonempty K, the recurrence
g:(K) = (K) + Σ bij gr- (K' (i))
JEK
enables computing per (J) by dynamic programming with ((2% arithmetic operations:
5

---

Function RPER(B)
RI (0( + 1, g0(K)) <- for c K C 1
R2 For _ J compute 9: (K) using 4
R3 i n then return g; else
+ 1, go R2
Having stored all the values ge K). generate random injection with probability proportional to ILee b753 in (Idd) steps by routine stochastic backtracking:
Function DSAMPLE(g)
D1 i i n, K J
D2 p(j) -- bij gi- gi-1(K (i))/((K) K. p(0) + ΣjEK pli)
D3 Draw p(j)
D4 j > then r(i) +- i, K + K {i}
D5 if = 1 then return (J); else i +- i 1, go to DI
To summarize, consider the depth-d variant of the Huber-Law bound, UHL, The matrix B can clearly be computed in time On?²), with J := {1, d}. Since U nests, the number of trials is (A) Aer/ e log 8-1), each of which can be implemented in time O by simple incremental computing (Supplement A.3). We have shown the following.
Theorem 1. (c. aapproxiimaaonnnn of the permanent of a given matrix with nonnegative entries can be computed, for any given 0 d S in time O (2 (A)/perA-n's 1-)..
An analysis for random matrices
We turn to the question of how well the approximation scheme based on the Huber-Law bound and its deep variant performs on the permanent of random matrix. Following previous works [2 14], we focus on (0, 1)-maticces of size with probability p. and write "A E ((n, p)" when A is a matrix in this model. We begin by stating and discussing main results: high-confidence upper bound for the ratio of the upper bound to the permanent, and its implication to the total time requirement of the approximation scheme. Then outline proof, deferring proofs of several lemmas (marked with *) to the supplement.
where the entries mutually independent, each entry being 1
4.1 Main results
In our analysis it will be critical to obtain a good lower bound for the permanent. To this end, we need the assumption that p does not decrease too fast when n grows.
Theorem 2. Suppose the function p p(n)) satisfies pºn - co as + cc. Let ō > 0. Then, for all sufficiently large n, B(n, p). and S S n - p-- with probability at least 1 25,
(A)
S 8- - d)) 1/2 (622 (62e-1(n ddyp)) 1/(2n0)
(5)
A
where Po = n 8-1
Remark 1. With sufficiently large, we could simplify the bound further by replacing Po with p. We present the more involved bound, as it follows more directly from our analysis and because we believe it is within small factor of bound that works also for small with moderate p and
Remark 2.
In the bound the key parameter is d rather than n, and the effect of d is linear in the base of the exponential bound. It remains open whether there exists a class of matrices where the ratio grows as c", c 1, for the depth-zero bound, and as c1--))n when the depth is pn.
The following time complexity result is immediate corollary to Theorems I and
Theorem 3. For any fixed > 1/2 and 5,p > O, an (e, apprrxximatnnn of the permanent of random matrix A B(n, p) be, with high probability, computed in expected time (+t

---

Huber's [17 closely related rejection sampling method, based on a slightly different nesting upper bound for the permanent, is known to run in expected time On ((11.5+0.6/p) for all (0, 1)-matrices where every row and column has exactly pn ones. Thus, our result extends Huber's also matrices where row- and column-sums deviate from the expected value, some more and some less. On the other hand, Huber and Law's 's [19] related scheme runs in expected time O( 1-5+0.5((2p-1) for all (0, 1)matriccss where every row and column sum is at least pn and p > 0.5; this bound, adopted also to the AdaPart scheme
22 Prop. IJ. is larger than the previous bound for all < 1.
We have also mentioned other Monte Carlo estimators that do not use rejection sampling. Their running time depends crucially on the variance of the estimator X, or, more precisely, on the so-called critical ratio []x])/E[X]² For random matrices, high-confidence upper bounds for this ratio have been proven for a determinant based estimator [22 [3] and a simpler sequential estimator [44, yielding approximation schemes that run in time ( to (n) (n)) and (tz (n) (n)), respectively; here & (n) = (n²)) the time complexity of computing the determinant, w(n) is any function tending to infinity n co, and t2 (n) equals n², n² In n, n n depending on whether p is greater than, equal to, or less than 1/3, respectively. We observe that the latter bound is worse than ours for p < 1/5 and better for p > 1/55, while the former bound, being Onn"), the best for p S 1/5.
The determinant based estimator has an important weakness: No efficient way is known for giving a good upper bound for the critical ratio for a given input matrix. Thus, either one has to resort to a known pessimistic (exponential) worst-case bound, or terminate the computations after some time with uncertainty about whether the estimate enjoys the accuracy guarantees. The latter variant is not "trustworthy." For further discussion and precise formalization of this notion, we refer to Frieze and Jerrum [13] Sec. 6]. They also point out that another estimator based on the Broder chain 6 20 is trustworthy and polynomial-time for random matrices- Hubiee [17 Sect. 3.1], however, shows that that scheme is slower than the rejection sampling based scheme.
Remark 3.
4.2 Proof of Theorem 2
outline
It is easy to compute the expected value of the permanent. It is also relatively straightforward to compute a good upper bound for the expected value of the Huber-Law bound (cf. Lemma 6 beloow). However, the ratio of these expected values only gives us a hint about the upper bound of interest; in particular, the ratio of expected values can be much smaller than the expected value of the ratio. To overcome this challenge, we use the insight of Frieze and Jerrum [13] that "[the permanent] depends strongly on the number of 1s in the matrix, but only rather weakly on their disposition." Accordingly, our strategy is to work conditionally on the number of 1s, and only at the end get rid of the condition.
For brevity, write V for perA and U for (A). Let M be the number of is in A. By a Chernoff bound, the binomial variable M is below mo == n²p
with probability most which is at most 5 if put a = n / 8-1, From now on, we will assume that M = m. with m 2 ma, and give an upper bound for U/V that fails with probability at most ò; the overall success probability is thus at least 28. The upper bound will be a decreasing function of m. and substituting the lower bound mo for m will yield the bound in the theorem.
-ppp-a2n22p-
For what follows we need that m' -2 tends to zero grows This holds under our assumptions, since mn 3/22 2 n2/2pp 3/22a, a, where the first term tends to co and the second to 0 as - oo.
We begin by considering the ratio of the expected values, E[U| M = mm/EE M m). For the denominator, we use a result of Frieze and Jerrum 13:
Lemma 4 (13 Eq. (4))). We have V M m] ni! / exp ( -
n² 2m
+ 1
n² }
For the numerator, we derive an upper bound by reverting back to the independence model, i.c.. without conditioning the number of 1s, for then the calculations are simpler. First, apply Markov's 's incquality to relate the two quantities:
Lemma 5 (+). P = mn 2 then EIU M m] < 2 E(U].
Then we use the concavity of the function h in Eq.
3 and Jensen's 's inequality.
Lemma 6 (+). We have B[U]= < (3) d! pd ed-a hp((n d)) n-d
Combining the above three lemmas and simplifying yields the following:
7

---

Lemma 7 (+). We have
EIU M m]
I e o ( d)/2)
1/2 ( 2020620-1p00 p. d)) 1/12m))
E M ml
where == mn 2, Furthermore, the upper bound decreases as a function of m.
Next we show that with high probability U is much larger and V not much smaller than expected. For the former, direct application of Markov's 's inequality suffices. For the latter we, again, resort to result of Frieze and Jerrum, which enables application of Chebyshev's 's inequality:
Lemma 8 113 Theorem 4J). We have E[V² M ml/B/p M m|² = 1 + On 7)
This yields the following upper and lower bounds: Lemma 9 (+). Conditionally on M m, we have with probability at least - 0x B (n2
a M = ml and V 2 (1-33)) M m].
We now choose a and 3 such that the failure probability is at most 6. Since n²m tends to zero as n grows, we could set to an arbitrarily small positive value, and a to any value smaller than 8. In particular, choose and / such that a (1 B) (On"( (e/2)) (e/2)-1/2 5-1 for sufficiently large n. Combining Lemmas] and 9 and substituting ma to m yields the bound (5)
Empirical results
We report on empirical performance study of DeepAR for exact sampling of weighted permutations and for approximating the permanent. We include our C++ code and other materials in a supplement.
5.1 Tested rejection samplers and approximation schemes
Both the Huber-Law bound and the Brouwer-Schrijyer bound are computed by applying function on each row and taking the product the results, and thus our dynamic programming method works with them. We have implemented the following instantiations of DeepAR:
HL-d: the scheme due Huber using the depth-d Huber- bound.
ADAPART-d: the AdaPart scheme using the depth-d Snnuwwr-SSchijver bound.
The time requirement per trial is Onn²) for HL-d and (n²)) for ADAPART-d, provided that there always a column which the Brouwer-Schrijer bound is nesting (Supplement A.3).
We ran the schemes with depths d {0, 20) and with and without preprocessing of the input matrix. The preprocessing is similar to one by Huber and Law [99] First, we ensure that every entry belongs at least one permutation of nonzero weight (36). Then we apply Sinkhorn balancing n² times 34 to obtain nearly doubly stochastic matrix (Supplement A.2). Finally, we divide each row vector by its largest entry. This preprocessing, we abbreviate as DS, takes O(n²) time. When the input matrix was preprocessed in this way, we add the suffix "-DS" to the names HL-d and ADAPART-d.
For comparison, also ran Godsil-Gutman type schemes (our implementations) and the original authors' implementation of AdaPart. Our main finding is that Godsil- type schemes are not competitive and that our implementation, ADAPART-O. is typically one two orders of magnitude faster than the original one: see Supplement C for more detailed report on these experiments.
5.2 Estimates of expected running times
We estimated the expected running time (ERT) of the schemes for producing (0.1, 0.05)- approximation of the permanent. Using GBAS 18), this yields a requirement of 388 accepted samples. To save the total computing time of the study, samples. By the argument Section 2. our estimate of the ERT has a relative error at most 50 % with probability at least 95 % (if we ignore the variation in the running times of rejected trials).
estimate the ERT based 65 accepted
We considered three classes of random matrices: Uniform the entries are independent and dis- tributed uniformly in [0, 1]; Block Diagonal consists of block diagonal matrices whose diagonal
8

---

Uniform
Diagonal
Bernouli(0. .2)
00
10a
a
Running time
10a
Be og
10
HL-20
HL-20
HL-20 HL-20-DS
HL-20-0S
HL-20-05
0%
00
Running time (5)
107
101
AdaPart-0 AdaPart 0 DS
AdaPart DS
AdaPart-0
AdlaPart-D
AdaPart DS
AdaPart 20:05
AdaPart 20
AdaPart 20
ndePart-29-DS
10"
20
110
140
170
200
20
40
80 100
40
100
Figure 2: Estimates of expected running times on random instances.
elements are independent x 5 matrices from Uniform (the last element may be smaller); in Bernoullipp), the entries are independent taking value 1 with probability and otherwise. In Figure 2 with HL-d on the upper row and ADAPART-d on the bottom row, we observe that on Uniform, deep bounds do not pay off and that the Huber-Law scheme is an order-of-magniuude faster than AdaPart. On Block Diagonal, deep bounds bring a significant, (wo-orders-of-magniuue boost and AdaPart is slightly faster than Huber-Law; furthermore, DS brings substantial additional advantage for larger instances (visible as smaller slope of the log-time plot). Bermoulli(p) again shows the superiority of deep bounds, but also case where DS is harmful.
We also considered (non-random) benchmark instances. Five of these are from the Network Reposi- tory (88 hhttp: /estp://networeee htwp//eewwwwoooeeeeeeee torr com, licensed under CC BY-SA), the same included by Kuck et 233 addition, we included Stairease-n instances, which are (0, 1) -matricess A (a:,) such that a, 1 if and only if i +i+ S n + 2. Soules (32) mentions these examples where the ratio the upper bound and the permanent particularly large. We observe (Table I that on four of the five instances from the repository, the preprocessing has relatively little effect, deep bounds yield a speedup by one to two orders of magnitude, and the configurations of AdaPart and which the Huber- bound
of size
Huber-Lan Law scheme about equally fast. The exception is cage5, breaks down without DS; closer inspection reveals that is due to row-sums that are less than 1. On the Staircase instances, deep bounds yield a dramatic speedup and DS makes a clear difference.
Table I: Estimates of expected running times (in seconds) on benchmark instances.
ADAPART-d
ADAPART-d-DS d=
HL-d
HL-d-DS
Instance
78
d=
d 20
d= 20
d=
d
20
d=
20
ENZYMES-PE -IEESS-g992
10a
1 1.10
10"
1.10"
1.
1 1.
6.10
10a
ENZYMES -230
32
30
1-
1-
1-
2-10²
1-
1.
2- 10a
ENZYMES -g79
28
3-
8-10
1-
8-10
1-10²
7-
7-
10
cage5
37
1.
2-10"
1-10
1.10"
> 10"
5-
9-
2-10'
bespwr01
39
6. 60
1-10"
4-103
2.10'
3.10²
1.10"
2.10
2-10'
Staircase-30
30
> 104
2. 10
9-
8.10
> 10
2.10
3.
7.
Staircase-45
45
> 104
10a
> 10
2-103
> 10
10
> 10
8 80

---

6 Concluding remarks
DeepAR (deep centtaancc-rjecttoonn boosts recursive rejection sampling by replacing the basic upper bound by deep variant. While efficient implementations of DeepAR to concrete problems remain to be discovered case by case, we demonstrated the prospects of the method on the permanent of matrices with nonnegative entries, an extensively studied hard problem. DeepAR enables smooth trading of precomputation for acceptance rate in the rejection sampling, and in our empirical study showed expedition by up to several orders of magnitude, as compared to the recent AdaPart method [23] (the original authors' implementation). The speedup varies depending on the size of the matrix and the tightness of the upper bound, and can be explained by three factors. A factor of 10-100 is due to implementation details, including both the different programming language and our more streamlined evaluation of the bounds for submatrices. Another factor of 2-1000 is due to our deep bounds. The third factor is due to the preprocessing of the matrix towards Soubsystochaasticity (DS), which yields large savings some hard instances, being mildy harmful for some others. A topic for further research is automatic selection of the best configuration (the permanent bound, depth, DS) on per-instance basis. There are also intriguing analytic questions (cf. Remark
Acknowledgements
Research partially supported by the Academy of Finland, Grant 316771.
References
[1] Dimitris Achlioptas and Pei Jiang. Stochastic integration via error-correcting codes. In Proceedings of the Thirty-Firsl Conference on Uncertainty in Artificial Intelligence, UAI 2015, pages 22-31. AUAI Press, 2015.
[2] Isabel Beichl and Francis Sullivan. Approximating the permanent via importance sampling with application to the dimer covering problem. J. Comput. Phys., 149(1): (99(1):12811)) 147, 1999.
[3] Ivona Bezáková, Daniel Stefankovič, Vijay V. Vazirani, and Eric Vigoda. Accelerating sim- ulated annealing for the permanent and combinatorial counting problems. SIAM J. Comput., 37(5):1429 115444442-1144,, 2008
[4] Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Evaluation of perma- nents in rings and semirings. Inf. Process. Lett., 110020) 2010.
[5] Lev M. Brëgman. Some properties of nonnegative matrices and their permanents. Dokl. Akad. Nauk, 211 211(1):2733,, 1973.
[6] Andrei Z. Broder. How hard it to marry at random? (on the approximation of the permanent). In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC 1986, pages 50-58. Association for Computing Machinery, 1986.
[7] Supratik Chakraborty, Kuldeep Meel, and Moshe Y. Vardi. Algorithmic improvements in approximate counting for probabilistic inference: From linear to logarithmic SAT calls. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, pages 3569-35777 3576. AAAI Press, 2016.
[8] Yuguo Chen and Jun Liu. Sequential Monte Carlo methods for permutation tests on truncated data. Stat. Sin, 17(3):8578872, 2007.
[9] Steve Chien, Lars E. Rasmussen, and Alistair Sinclair. Clifford algebras and approximating the permanent. J. Comput. Syst. Sci., 67(2)2633-290, 2003.
[10] Paul Dagum, Richard M. Karp, Michael Luby, and Sheldon M. Ross. An optimal algorithm for Monte Carlo estimation. SIAM J. Comput., 29(5): 148441446444 2000.
[11] Jeffrey Dudek, Dror Fried, and Kuldeep S. Meel. Taming discrete integration via the boon of dimensionality. In Advances in Neural Information Processing Systems, volume 33, pages 1071-1082. Curran Associates, Inc., 2020.
10

---

[12] Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, and Bart Selman. Taming the curse of dimensionality: Discrete integration by hashing and optimization. In Proceedings of the 30th International Conference on Machine Learning, ICMI. 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 334-342. .or..orgg 2013.
[13] Alan Frieze and Mark Jerrum. An analysis of a Monte Carlo algorithm for estimating the permanent. Combinatorica, 15(1), 1995.
[14] Martin Fürer and Shiva P. Kasiviswanathan. An almost linear time approximation algorithm for the permanent of random (0-1) matrix. In Proceedings of the Twenty-Found International Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, volume 3328, pages 263-2711 163-274. Springer, 2004.
[15] David G. Glynn. The permanent of square matrix. Eur. J. Comb., 3 (7):1887-1891, 2010.
[16] Christopher D. Godsil and Ivan Gutman. On the matching polynomial of graph. In Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis János Bolyai, number 25, pages 241-249, North-Holland, 1981.
[17] Mark Huber. Exact sampling from perfect matchings of dense regular bipartite graphs. Algo- rithmica, 44(3):183-193, 2006. 2006.
[18] Mark Huber. A Bernoulli mean estimate with known relative error distribution. Random Struct. Algorithms, 17-2):773-182, 2017.
[19] Mark Huber and Jenny Law. Fast approximation of the permanent for very dense problems. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pages 68 1819.9 Society for Industrial and Applied Mathematics, 2008.
[20] Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):114) 149 1178, 1989.
[21] Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of matrix with nonnegative entries. ACM, 51()))671-6)) 2004.
[22] Narendra Karmarkar, Richard Karp, Richard Lipton, Lazlo Lovász, and Michael Luby. A Monte-Carlo algorithm for estimating the permanent. SIAM J. Comput. 22(2):284 293,, 1993.
[23] Jonathan Kuck, Tri Dao, Hamid Rezatofighi, Ashish Sabharwal, and Stefano Ermon. Approxi- mating the permanent by sampling from adaptive partitions. In Advances in Neural Information Processing Systems 32, pages 8860-8871, Curran Associates, Inc., 2019.
[24] Henryk Mine. Upper bounds for permanents of (0, 1)-matrices. Bull. Amer. Math. Soc. 69(6)7789779, 1963.
[25] James E. Newman and Moshe Y. Vardi. FPRAS approximation of the matrix permanent in practice. CoRR, abs/2012.033667. 2020.
[26] Roger Paredes, Leonardo Dueñas- Dueñas-Osorio, Kuldeep S. Meel, and Moshe Vardi. Principled network reliability approximation: A counting-based approach. Reliab. Eng. Syst. Saf., 191:93- 110, 2019.
[27] Lars E. Rasmussen. Approximating the permanent: A simple approach. Random Struct. Algorithms, 5(2):349-33) 362, 1994.
[28] Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conference Artificial Intelligence, pages 4292-4293. AAAI Press, 2015.
[29] Herbert J. Ryser. Combinatorial mathematics, volume 14. Mathematical Association of America, 1963.
[30] Alexander Schrijver. A short proof of Minc's conjecture. J. Comb. Theory Ser. A, 25(1)80083, 1978.
11

---

[31] Peter J. Smith, Hongsheng Gao, and Martin V. Clark. Performance bounds for MMSE linear macrodiversity combining Rayleigh fading, additive interference channels. J. Commun. Networks, 4(2):102-107, 2002.
[32] George W. Soules. New permanental upper bounds for nonnegative matrices. Linear Multilinear Algebra, 51(4):119-333 2003.
[33] George W. Soules. Permanental bounds for nonnegative matrices via decomposition. Linear Algebra Appl., 393:73-99: 090339999880 2005.
[34] Francis Sullivan and Isabel Beichl. Permanents, a-permanents and Sinkhorn balancing. Comput. Stat., (9(6):1733-173) 2014.
[35] Topi Talvitie, Kustaa Kangas, Teppo Niniimäii, and Mikko Koivisto. A scalable scheme for counting linear extensions. In Proceedings of the Twenty-Sevnnth International Joint Conference on Artificial Intelligence, IJCAI 2018, pages 51 19-5125. ijeai.org, 2018.
[36] Tamir Tassa. Finding all maximally-matthhbbl matchable edges in bipartite graph. Theor. Comput. Sci., 223:50-58,20 2012.
[37] Jeffrey K. Uhlmann. Matrix permanent inequalities for approximating joint assignment matrices in tracking systems. J. Frankl. Inst., 341(7)559--593, 2004.
[38] Leslie G. Valiant. The complexity of computing the permanent. Theor, Comput. Sci., 8(2):189- 201, 1979.
12


Reviews:
[{"review_id": "q7iTSakm2CB", "reviewer": "Reviewer_3uKV", "summary": "The paper proposes a randomized method for estimating the permanent positive matrix. It uses a recursive rejection sampling method but with a more fine-grained upper bound and provides an efficient way to compute it. They provide theoretical analysis on expected running time for random matrices, where the bound is superior for certain regimes of p, and provide compelling empirical experiments to show practical improvement over prior methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper is well-structured, has nice theoretical results with competitive practical performance. It is a good step toward understanding  efficient permanent approximation algorithms. I only have three small concerns regarding the work:\n\n1) I am not sure NeurIPS is the best venue for this work, as it is quite theoretical, and I am unsure about how significant it is a problem of estimating permanent for the general machine learning community.\n\n2) The framework seems to rely heavily on the recursive rejection sampling method in prior work, and the main novelty in idea is the deep bound depending on depth instead of a uniform bound to increase acceptance probability for better efficiency. \n\n3) Also, the runtime has an infavorable 2^d factors, which doesn't seem very scalable.\n\nI would be happy to increase my score if authors offer compelling arguments against my concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, in sections 4 and 5.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "obCp-66LQxb", "reviewer": "Reviewer_kjA5", "summary": "Computing the matrix permanent is known as a #P-complete problem and no exact polynomial-time algorithm is known. Several works developed a randomized algorithm for approximating the permanent of a non-negative matrix based on recursive acceptance-rejection (AR) sampling and various upper bounds of permanent. This paper adopts a deep AR sampling scheme that skips some recursive steps. Then, the authors additionally propose an efficient way for computing skipped steps based on dynamic programming of permanent. Empirical results demonstrate order-of-magnitude savings of computational time under random synthetic and real-world datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of this work is boosting recursive sampling by skipping intermediate steps. Although the method is simple, the authors additionally propose an efficient way of computing the upper bound at depth d. This is a novel approach that utilizes the key properties of permanent. Furthermore, experimental results show a huge gap of computational savings under real-world datasets. \nSome questions are the following:\n- In Theorem 1, it is clear that the running time depends on the depth d, but unclear how the depth affects an approximation quality. It would be great if the approximation quality is provided in terms of the choice of depth.\n- The depth can be specified by the user, but the algorithm varies on the choice of the depth. Is it possible to theoretically/empirically predict the optimal value of depth? Simply, does the optimal depth that minimizes the running time of the algorithm provided in Theorem 1?\n- In section 5, what is the approximation quality (or accuracy) of each benchmark algorithm?  It would be great to provide accuracy comparison.\n- Additionally, it would be much better if the paper is polished more so that it can be much easier to understand the proposed algorithm and related works.\n\nMinor questions:\n- In equation (2), does the summation over all permutations \\sigma of S drop?\n- Is the \\gamma (in line 114-115) well-defined for k=0?\n- The toy example provided in section 4 seems to be related to an adjacency matrix of Erdos-Renyi graph. If so, the proposed algorithm can estimate the number of perfect matchings of a given graph. Some readers may welcome it if the paper provides a corollary of perfect matching counting algorithm.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Described above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "_-cDWVB1_W", "reviewer": "Reviewer_EvRy", "summary": "The authors addressed the efficient approximation of permanent of a matrix with nonnegative entries. The proposed scheme is based on the recursive rejection sampling method by Huber 2008, but the upper bound on the permanent is based on the linear combination of the subproblems with the deep recursion tree. The expected running time is both theoretically and experimentally analyzed. ", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the research is quite interesting overall. The algorithmic idea (previous rejection sampling-based method with deep bounds), related work, algorithm, results, proof sketch are quite well presented. Both theoretical and numerical performance improvement is quite significant. Due to the importance of the problem of permanent computation, I believe that this result will be very valuable. \n\nThe only comment I can make is that Theorem 2 is not directly compared with the complexity result in [23]. I think it is fair to make an accurate comparison including both improvements and limitations. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "IDxWgJCOxq", "reviewer": "Reviewer_8km5", "summary": "The paper gives a new algorithm to approximate permanents of non-negative matrices. The method builds upon the well-known rejection sampling method by Huber-Law (SODA'08). The algorithm is experimentally shown to perform well, and in particular better than the related result by Kuck et al. (NeurIPS'19). Finally, a mathematical analysis of the performance of the algorithm on a family of random matrices is given, where it is shown to run in polynomial time to yield arbitrarily good precision.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies approximating weighted counting problems such as the permanent using an idea based on self-reducible rejection sampling by Huber-Law. This is a well-studied heuristic for approximating permanents. Roughly speaking, in this method we have a certain upper bound on the permanent per(A)<=U(A) and we keep sampling permutations (according to a specially crafted distribution resulting from self-reducibility) until we have seen at least K \"yes\" samples. Finally the estimate is given by U(M)*K/T, where T is the total number of samples drawn. It is not hard to see that the running time of this method depends on the quality of the upper bound U(M) and what this paper achieves is replacing this bound by a tighter one. The new bound U_d(M) obtained in this paper is a generalization of the Huber-Law bound, based on a kind of d-level deep look-ahead in the tree that is used in the sampling process. The regular Huber-Law bound U(M) is U_1(M).\n\nThe presentation of the paper's results is clear and the paper is generally easy to read. The basic idea of self-reducible rejection sampling is explained with enough details before moving on with the presentation of this paper's contribution: deep rejection sampling.\n\nThe first result in the paper (Theorem 1) asserts that in time roughly O(2^d*dn + U_d(A)/per(A)*poly(n, 1/eps)) one can compute an eps-approximation of the permanent per(A) of an nxn matrix with >=0 entries (with logarithmic dependency on the error probability). In general, it is not simple to give reasonable bounds on U_d(A), hence the authors provide an analysis of U_d(A) for random Bernoulli matrices. They show (Theorem 2) that in this case the algorithm runs in polynomial time, and beats known results in the regime where p (the probability of an entry being 1) is <1/5.\n\nMost of the proofs are delegated to the supplementary materials, yet the provided overviews are valuable and allow to shape some intuitions.\n\nAuthors provide an empirical evaluation of their results comparing their algorithm with the one by Kuck et al. When presenting the results it would be much cleaner if both methods were plotted on a single diagram instead of having separate diagrams per method -- this way it is not clear how do they compare (which seems to be the main point of this experiment).\n\nWhen assessing the paper I had the following doubt: shall I consider it as A) a theoretical paper with the main contribution being the mathematical theorems, or B) an applications-focused paper, giving a practical heuristic for counting problems. When treated as A) I have concerns that the contribution of this paper over previous work (Huber-Law and then Kuck et al.) is not that significant and hence I would not place it among top papers. When treated as B), I felt that this paper does not provide enough discussion on *concrete* possible applications in learning and what the concrete impact of this new method could be.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a generalization of an algorithm of Huber and Law for approximating the permanent of a non-negative matrix (an important and basic counting/sampling problem). The idea is to combine the rejection sampling method of Huber and Law with a deep (parameterized by some depth parameter d) "look-ahead" that uses a linear combination of sub-problems at depths <= d in the recursion tree as an upper bound on the permanent. This theoretically strengthens the guarantees of Huber and Law (and beats them on the "toy" example of random Bernoulli matrices. In experiments it beats the guarantees of a recent work of Kuck et. al. in approximating the permanent. 

There were concerns that the theoretical contributions of the paper are not strong enough on top of prior work. However, the relatively clean and simple look-ahead method (deep AR) developed in this paper does give a significant advantage in terms of practical speed-ups. The deep AR heuristic, as a result, appears an appealing avenue to explore further. We recommend acceptance. 
Decision: Accept (Poster)