Trustworthy Monte Carlo
Authors: Juha Harviainen
Mikko Koivisto
Petteri Kaski
Venue: NeurIPS 2022 Accept (2022)
Keywords: Algorithm
Approximation scheme
Estimation
Monte Carlo
Probabilistic inference
Sampling
Theory
Verifiable

Abstract: Monte Carlo integration is a key technique for designing randomized approximation schemes for counting problems, with applications, e.g., in machine learning and statistical physics. The technique typically enables massively parallel computation, however, with the risk that some of the delegated computations contain spontaneous or adversarial errors. We present an orchestration of the computations such that the outcome is accompanied with a proof of correctness that can be verified with substantially less computational resources than it takes to run the computations from scratch with state-of-the-art algorithms. Specifically, we adopt an algebraic proof system developed in computational complexity theory, in which the proof is represented by a polynomial; evaluating the polynomial at a random point amounts to a verification of the proof with probabilistic guarantees. We give examples of known Monte Carlo estimators that admit verifiable extensions with moderate computational overhead: for the permanent of zero--one matrices, for the model count of disjunctive normal form formulas, and for the gradient of logistic regression models. We also discuss the prospects and challenges of engineering efficient verifiable approximation schemes more generally.

Trustworthy Monte Carlo
Juha Harviainen University of Helsinki
Petteri Kaski
Aalto University
juha. www.haainneeeelllsiieee...
petteri kasteri. fo
Mikko Koivisto
University of Helsinki
mikko koivisto@helsinki..
Abstract
Monte Carlo integration is a key technique for designing randomized upproximation schemes for counting problems, with applications. e.g., in machine learning and statistical physics. The technique typically enables massively parallel computation, however, with the risk that some of the delegated computations contain spontaneous or adversarial errors. We present an orchestration of the computations such that the outcome is accompanied with proof of correctness that can be verified with substantially less computational resources than it takes to run the computations from scratch with state-of-the-art algorithms. Specifically, we adopt algebraic proof system developed computational complexity theory, in which the proof is represented by a polynomial; evaluating the polynomial at random point amounts to a verification of the proof with probabilistic guarantees. We give examples of known Monte Carlo estimators that admit verifiable extensions with moderate computational overhead: for the permanent of zero-one matrices, for the model count of disjunctive normal form formulas, and for the gradient of logistic regression models. We also discuss the prospects and challenges of engineering efficient verifiable approximation schemes more generally.
1
Introduction
Can we trust a result computed by a machine? Putting aside questions about the sensibility of the computational task itself, trust stems from one's belief in the correctness of the selected algorithm, its implementation in software, and execution on hardware. All these ingredients are prone to errors, especially when the task is hard, the algorithm is advanced, and the computations are extensive (distributed and long). Trustworthy computation is one pillar of trustworthy Al (88,, and it an issue particularly when one "outsources" computations other computational agents, e.g., millions of Internet users to make use of their idle cycles-sone some users could be dishonest and return seemingly
valid results without running any actual computation 6 26).
Ideally, the outcome of the computations would be accompanied with a certificate of correctness, or proof. the user can verify. Furthermore, verification should be computationallyy easy in that it should consume substantially less computational resources than it takes to run the computations from scratch with state-of of-te-of-the--ae -tet--rtt algorithms. For many decision and search problems such proofs are available; e.g., certificate of satisfiability of a given Boolean formula is simply a satisfying truth assignment. For optimization problems, the cost of the found (locally optimal) solution is typically easy verify, and certificates of optimality are sometimes obtained by linear programming duality. Certifying algorithms extend the output accordingly with easy-to-verify proof (20). For counting problems, which are central in applications involving probabilistic reasoning, such certificates are typically not readily available, and it is immediate whether such certificates exist in the first place.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we initiate research on verifiable randomized approximation schemes for weighted counting. Specifically, we investigate Monte Carlo estimators, which approximate a target quantity j by sample-average of random variables W1, W2,..., WN with mean / so that
N
R N
W
(1)
1=1
For an accurate estimate, one may have draw large number of samples. Fortunately, the simple way of aggregating the N samples enables easy and efficient parallelization of the computations, particularly if the samples are independent. This motivates studying setting where one agent, the verifier, delegates most of the computations to one or more other, potentially computationally more powerful, agents. When aggregating the results of the delegated computations, how can the verifier know if some agents made errors, whether intentional or spontaneous, in their computations?
To address this question, we build ideas and frameworks developed in the context of proof systems with probabilistic soundness in complexity theory and cryptography (9] g 26] 27]. One of the key ideas is to encode the problem instance at hand by univariate polynomial p of degree D such that knowing the D + coefficients of p-or equivalently, evaluations of p at D + 1 points-reveals the correct solution to the problem instance. The verifier delegates the task of computing p and receives claimed polynomial p. Now, the verifier evaluates both the correct p and the claimed p at a single random point r drawn from a range significantly larger than D: if p A p. then p(r) A p((r with high probability, since p p has at most D roots. Supposing the total time needed for solving the problem with state-of-the-art algorithm is T ~ DE, where E is the time requirement per evaluation of p, an optimal verifier time is achieved when D E se VT. That is, verification computationally easy in the sense that it consumes essentially only square root of the resources needed to solve the problem with state-of-the-ar algorithms. Various problems can be cast in this way, with only a small overhead in relation to the time requirement of the corresponding vor-iieiiia computation. Examples range from the matrix permanent and model counting for Boolean formulas [27] to graph coloring and counting small subgraphs 4 and to exact probabilistic inference in graphical models [14].
When extending the framework to Monte Carlo estimators of the form ( we encounter new challenge: the randomness and independence of the summands W.. Indeed, if the verifier outsources the generation of random numbers, there is no deterministic correct result that could be verified. We circumvent this obstacle by letting the verifier generate all needed random bits, after which the remaining computational task deterministic. This leads another challenge: if the verifier has to generate N random numbers, how can the verifier avoid its running time scaling as N, the goal for scaling being rather /N? Here we make use of the facts that (i) only Olog N) independent random bits suffice to generate N pairwise independent random bits, and (ii) pairwise independence suffices for concentration results that stem from bounding the second moment of the random variables W..
The rest of this paper is organized as follows. Section 2 connects the task of designing proof polynomial to that of finding an appropriate low-degree arithmetic circuit [27]. In Section 3, we present our main contribution, a generic method for obtaining what we call verifiable randomized approximation scheme (vras). Section 4 extends the method to settings where our arithmetic circuit only approximates a random variable W.. As running example, we use the problem of computing the permanent of given matrix, for which practical approximating schemes have been sought in the AI community recently [18 10]. We also apply the methods to known Monte Carlo estimators for model counting of Boolean formulas given in a disjunctive normal form and for estimating gradients of a Bayesian logistic regression model. In the last section, we connect to recent work on learning and reasoning with arithmetic circuits 25 and probabilistic generating circuits 29 We also discuss directions for future research.
Although this work is theoretical and leaves experimentation for future works, we include a proof-of- concept Mathematica [II] implementation for the example of Section Doctioon3.4fin in the supplement.
Throughout the paper, the notation Ô(:) suppresses factors polylogarithiic in the argument, [P] evaluates to 1 if P is true, and to 0 otherwise, and (f) marks that a proof is given in the supplement.
2 Proving and verifying with polynomials
We begin by introducing the proof system, synthetisizing ideas from related recent works 27
2

---

For constructing a verifier, the idea is to represent the essence of the computational task as evaluation of univariate polynomial p(x) = Po + pix² +.... PD= over finite field F' at some 2 D + distinct points {1, f2...., & E F, selected so that given the values p(()),(({))...... (.(s)))....((())))))))))))))))). a 2.1 Prove and verify
Suppose one computational agent, the verifier, wishes to delegate most the computational task at hand to another agent, the prover. Here the prover may consist of multiple agents working independently of each other, thus efficiently parallelizing the delegated computations.
Definition 1.
Let be an algorithm with access to another algorithm B. We call A a verifier and B prover, if given any problem instance, the output of A is correct whenever the output of B is correct [ and otherwise A outputs "untrusted" with probability at least 2/3. We refer to the time requirements of A and B as the verifier time and the prover time, respectively.
The constant 2/3 is customary but arbitrary. As we will point out soon, the probability can be efficiently amplified arbitrarily close to 1.
they are correct the verifier can, with little additional work, solve the original problem. Crucially, the correct polynomial is specified by the problem instance in a way that is known to both the verifier and the prover. From the verifier's viewpoint the procedure is follows.
Algorithm V
V1 Send the prover the problem instance and the points E1,E2,-.. E2,-..,,.. ,e--
V2 Receive from the prover proof, i.e., a claimed value of p(Ex) ) for each k = 1,,,..... e.
V3 Find the coefficients of p(x)) Peo such that p(Ex) = yu for all k = 1.,,...,e.
V4 Draw random point &u E F and evaluate p(Eo) and p(5o).
V5 If p(Eo) = p(Eo), then accept the proof and consume the values y&: otherwise reject the proof.
Note that if 5 * p, then p(Eo) p(Eo) with probability D/ which can make arbitrarily small by using a finite field F that sufficiently large in relation the degree D.
Several remarks are in order. While D + evaluations would suffice for recovering the polynomial, we allow e 2 D + to enable error-correction. Indeed, as long as at least (e + D + 1) 2 of the evaluations are correct, the correct polynomial can be efficiently recovered using Reed-Solomon decoder (see [4] and references therein); e.g., putting = 2(D + 1), one fourth of the prover's s evaluations can be incorrect. The procedure also enables the prover to run the evaluations in parallel on e computing units without any communication among them. Furthermore, the protocol is, in essence, non-interactive: the verifier only sends message the prover and receives one. Finally, in step V3 the computational efficiency of the procedure stems from fast interpolation of univariate polynomials; this is incorporated in Theorem I given in the next section.
2.2 Multipoint circuit evaluation
For designing the polynomial and selecting the evaluation points, adopt Williams's [27] generic method, with some changes. The idea is to represent the problem at hand as a task of evaluating an arithmetic circuit multiple points. This approach differs from that of Björklund and Kaski [4, who craft their polynomials separately for each problem they consider to obtain a mneigraieed optimization of the running time.
An arithmetic circuit C in variables æ1, .2, Fy over a field is a directed acyclic graph, in which each vertex is called gate and labeled by + (sum) or (product) if its in-degree is not zero, and otherwise by one of the variables x; or by constant from F. Every gate computes a polynomial C. E F[ .2..... xn in obvious way. Unless stated otherwise, the circuit is assumed to have single output gate u (i.c., of out-degree zero) and C' is identified with the polynomial C., The size,
We understand a problem as a map from a set instances a set solutions, and that given an instance I, an output S of an algorithm for 11 is correct and only if 11(1) = S. By saying that A has access to B we mean that A can run B to solve instances of a fixed subproblem 11', in relation to which an output of B is either correct incorrect.
3

---

22
y1
12
An arithmetic comparison circuit. The circuit outputs if æ < y, and 0 otherwise. The numbers x and are given as bit vectors of length n.; illustrated is the case = 2. The circuit represents the polynomial Σ (1 n. I 1-1
Figure 1:
(1 - (1 x3 )u5)) of degree 2n using (n)) gates.
depth, and degree of are, respectively, the number of gates, the length of the longest directed path, and the largest degree of the monomials in C. We assume that the maximum in-degree is at most 2.
Arithmetic circuits are powerful representations of functions and computation. For example, to simulate any Boolean circuit by arithmetic circuit of about the same size and depth, simply replace each Boolean gate by a constant number of sum and product gates, e.g., 31 22 by æ + x22 2 Figure shows circuit for comparing two n-bit nonnegative integers.
Typically we want to show that given function admits circuit that has small size and low degree. While it is important that we can also efficiently construct such a circuit, usually it is clear that construction takes time roughly linear in the size of the circuit, and we do not mention that.
The multipoint circuit evaluation problem (MCE) is as follows. Given an arithmetic circuit C' in n variables over finite field F' and points u u² ..... uk E F", compute the values C(u²) E F for all = 1,2, K. Denote by s and d the size and the degree of the circuit, respectively.
The following result tells that we can design verifier by representing the problem as instantiation of MCE, We attribute the result to Williams [27] Theorem 1.2]; we have made some modifications to the proof to also take into account the prover's time requirement (not considered by Williams).
Theorem (t). MCE admits a verifier with prover time Ö(Kds) and verifier time Ö(Kdn + s).
Proof sketch. The main idea is to transform the circuit C' of variables into univariate circuit p. which then represents a univariate polynomial. We associate each point E F" with an element E from some large enough extension field F of F. Next, find interpolating polynomial for each variable of C' such that for a point & the polynomial X, extracts the jih component uz of w'. As result, we obtain circuit with p({:) = C(ui, ".. ".)).
The interpolating polynomials increase the degree of the circuit (polynomial) by factor of K, and therefore we need Kd + evaluations to determine the polynomial representation of p uniquely. As a consequence, we evaluate p on some additional arbitrary distinct points f .......... EK4+1
The prover needs to evaluate a circuit of size s on Kd + points, which takes time O(Kss). On the verifier's side, need to send the circuit of size to the prover, as well as input variables of C' for each point & to enable massive parallelization. This and the other steps of Algorithm V can be computed efficiently in given time limits by using fast interpolation and multipoint evaluation of univariate polynomials.
Remark 1. The result relies on the prover's and the verifier's ability to evaluate the circuit in a given point from F", where F is an extension field of F. For the time requirement of these evaluations, the circuit size 8 gives an upper bound, which can overly conservative-indees term by the actual time required for computing the value of the circuit at a given point. For example, the univariate polynomial it can be evaluated in the form (1 2d+1) 1/11 z) using only O(log d) field operations.
we may replace the
+ ....... xd in one variable has circuit size 2d and degree d, but

---

2.3 Example: the permanent
The permaanet of square matrix A (as,g)
Fmxm is given by
m
perA
EII (i,
Σ (e(0.1)
II -
where o runs through all permutations on 2., The second expression is due Ryser 22
Assume m is even and put n = m/2 and
m
C(I) = II
hays and C.(u): :=
Σ
C(ui, U2, Un. U1, U2,..., Un)
DE [0,
Now PerA = (o (.).. Write (-1)1 as 2f; - to observe that C, has an arithmetic circuit of size 0(2"m²² and degree 2m. By Theorem 1 the permanent admits verifier with prover time ) and verifier time 0(2m/2).
3
Verifiable Monte Carlo integration
We next apply Theorem | to the computation of Monte Carlo estimators ①
3.1 Multipoint evaluation and pairwise independence
To reduce the Monte Carlo estimator to circuit evaluations, we simply write the sum over N terms double summation:
N/K V = Σ W W(--1)K+J-
Σ
W.
Σ
V&
N
Naturally, has to divide N. To make this hold, we will assume that N and K are powers of 2.
Now view each random variable V₁2 point =. In fact, we take the index & itself as the point u² The eircuit is obtained as a sum of K/M evaluations of smaller circuit C, each of which outputs W W(k-1)K+) when given & and j input. Crucially, the output of C' is deterministic function of (k: implying that all randomness must be encoded in C. Because of this, the random variables cannot be independent, for then the encoding would require at least N bits, rendering the circuit C' large and undermining the pursuit of an efficient verifier. To circumvent this obstacle, we resort to pairwise independence.
output of a fixed arithmetic circuit evaluated some
To develop these ideas more formally, we begin with the fact that É independent random bits suffice for generating 2 1 pairwise independent bits, by taking the exclusive-or of every nonempty subset [22 Lemma 13.1]. We may index by a bitvector é {0, 1)"h interpreted as the integer f +22 +.. 2 2 te.
Definition 2. The subset-sum expansion of x E {0, 1}. is the bit vector y E {0, 1] given by
+ t.z, O., 0) 13
Vt
Fact Let x be a uniform draw from {0. 1 and y its subset-sum sum expansion. Then the bits y are pairwise independent uniform draws from {0, 1).
Clearly, if the index is given as a bit vector, the bit y, can be computed by a succinct circuit:
Proposition 3. Given a bit vector x E {0, 1 there is a circuit C FF + of size O(E) and degree such that C(t) = for all t E {0, 1 (..0,,.....0. 0)), where y is the subset-sum expansion of x.
Proof. The first layer computes 2, = 422, for = 112,...,4 The second layer computes the exclusive-or of 21, 22...., 2t using the arithmetization o a(1 - (1- aaa a+bb b-bbb D
5

---

A single random bit yt being generally insufficient for generating the random variable W of interest, we take n independent copies, where n will be set depending on the specific random variable.
Lemma 4 (t). Let C F + F be circuit of size and degree d. Let N S 2 - 1 be a power of
2. Then, given bit vectors x' x²,x², ,....,"" E {0, 1) and a factorization N = -2"2", there is a circuit
C. : F - of size ( (En + 8)) and degree Ed, such that
N
Σ C.(u) = Eowl
Clul v ve...................
where y E 10, is the subset-sum expansion of
3.2 Verifiable approximation schemes
So far we have required that the verifier's output is correct if the prover's output was correct (Definition[[] [T. While this applies to computing Monte Carlo estimators (with a fixed sequence of random bits), as shown above, we find convenient to extend the definition so that the verifier's output is only required to have probabilistic error guarantees. We focus on conrolling the relative error; call a random variable Z an (e, 8)approximmaioonn of a real r if Pr(IZ/T - 1| > E) <
-1 Definition 3. Let A be an algorithm with access to another algorithm B. We call verifiable randomized approximation scheme (vras) if, given an instance and tolerance parameters e, > O, it outputs an (c, -apppoxximationn whenever the output of B is correct, and otherwise outputs "untrusted" with probability at least 2/3. We refer to A and B as the verifier and the prover and their time requirements as the verifier time and the prover time, respectively.
If a Monte Carlo estimator is an (c. approooxxiiio for sufficiently large N, we obtain vras by applying Lemma annd Theorem Typically, for averages of 0-1 random variables in particular, such estimators are derived using Chernoff bounds assuming independent samples, which we do not have here. Fortunately, pairwise independence suffices for concetration results based on the second moment; Chebysev's 's inequality only needs control of the critical ratio R[W3)/ [[W]
Theorem 5 (t). Let W be a random variable with the critical ratio at most a known upper bound R. Suppose there is an arithmetic circuit C: F > FF of size s and degree d such that W C(x) for x drawn uniformly at random from {0, 1}". Then the mean W admits vras with a prover time ÖTT) and a verifier time Õ(VT= + + d dlog@ 8-)), where T == R d S. c- 1n6-1.
Note that the total work T is essentially up to the factor d and the hidden polylogarithmic factors the same as the requirement of the baseline algorithm that does not enable verification. Usually the term /T dominates the verifier's time requirement. Recall that we implicitly assume that the circuit can also be efficiently constructed for the given problem instance. The challenge is, however, rather to show that the random variable W can be generated by a low-degree circuit.
3.3 Example: The GoussilGuttman estimator for the permanent
Let A = (azy) be an m x m binary matrix and B (biy) an m m matrix where by are independent uniform draws from {-aiy. 3 C (-1, 0, 1). One can show that [(det B) perA. Employing this observation, the Godsil-Gutman estimator 77 for the permanent is given by N Σ Wt. where We are copies of W := (det 33 The critical ratio of W is at most 3m/22 [5].
We show that the permanent admits a vras. By Theorem S suffices to give an arithmetic circuit C' that computes W given some number n of random bits as input. We put == m² so that there one random bit Zıj per matrix entry. The first layer of C' constructs B by bij == (1 2x..) Jasj- The second layer computes the determinant of B using, e.g., Berkowitz's 's division-free circuit of size O(m²) : fact, by Remark we may use division and replace the bound by ( The last layer raises the obtained result to the second power. Since the degree of the determinant is m, the degree of the circuit is 2m. By Theorem 5 the prover time and verifier times are Ö(T) and Õ(VT), where T = 3mm/2, -2 In 8-1, ignoring a factor polynomial in m. The circuit is defined over the field Z./qZ, where g is large prime; is sufficient to have q 2 2N (n.)² so that the arithmetic does not overflow. Large primes can be efficiently found (2)

---

3.4 Example: A quaternion based estimator for the permanent
more sophisticated Godsil-Gutman type estimator [5] uses a random matrix B whose entry big is zero if aij = 0, and otherwise an independent uniform draw from the signed quaternion basis +i,, =j. =k}. Representing the four basis elements, respectively, by the complex-valueds 2 x matrices (. (b ).. (-1 b). and (i i), and letting D (diz) be the corresponding 2m x 2m matrix representation of B, the random variable of interest is W ;= det D. The mean of W equals
perAA and the critical ratio of W is at most (3/2)m/² m22 [3]. improving on the basic estimator
Accordingly, we can apply Theorem 5 to show that the permanent admits a vras with a prover time Ö(T) and a verifier time O(vT + log 8-)), where T = (3/2)m/²2 1n Now our circuit to compute W takes as input 3 random bits xr y. 2 per entry Dij of A and puts
(1-y)(2M) (d2i d2i-1.20) )= == a.,(1 - 2x) [u[2M + (1 M) + (1 - (2Ms + (1 (1-11111100 (111-2)M0 M) d2..2-11
d2:22
where M1, M2, M3, M4 are the x 2 matrices given above. Thus the degree of each entry of 3, whence the degree of det D is 6m. The circuit is defined over Z/9Z, with appropriate prime q: we require q 2 2N (n!)² to avoid overflows and, additionally, that = mod 4 to guarantee that the field has fourth roots of unity (to serve as i, -1, -i, and 1); the roots can be efficiently found [T]
4 Extensions for approximate circuits
So far we have assumed that the random variable W can be exactly computed by a succinct arithmetic circuit. We next extend the method to allow for circuits that only approximate the random variable.
4.1 Small deviation with high probability
Clearly, to obtain (c, approxximation, the expected value of the circuit need not be exactly that of W- achieving a relative error of order (c) should suffice. Likewise, the shape of the distribution need not be similar to that of having reasonable upper bound for the critical ratio should suffice. Moreover, we may let the circuit fail and not deliver these features with a small probability or order O()). We next formalize this intuition.
For a random variable Y and event A, write o [||[A] for the standard deviation of the conditional distribution, i.e., for the (nonnegative) square root of the conditional variance E|Y² AA] - ||}]
Definition 4. Let Fs, Pt) be probability spaces and X; S2 IR random variables, i {1, 2). e 8 E [0, 1]. We say that X2 is an (e, 8) dddeiiate of X if there exists an acceptance event A E F2 such that (A)
8 and [E[X2|A] and o [X2 A] approximate [[[1] and o [[Xi] to within relative error of e and 1, respectively.
Our choice of the upper bound 1 for the relative error of the standard deviation is somewhat arbitrary. One may replace it by any small number, incurring only a respective small factor to the running time.
Corollary (t). Let W be a random variable with the critical ratio at most a known upper bound R. Suppose that, for any ạ == (a, 3) E (0, 1)², there is an arithmetic circuit Cy FF - F of size 8n and degree dy such that (xx is an (ar, ---viiaaeee of W when x. is drawn uniformly at random from {0, 1)"r. Then, for any a & </3 and 3 S de2 (3456R (n(2/))). the mean of W admits an (c, 8) -vras with a prover time Õ(T) and verifier time Ö(VT + Sy + d, log 8)1), where T : R- dy, S., EE" Ind
We have not optimized the constants. Note also that expect the parameter 3 to affect the circuit size and degree only logaritmically, i.c., by factor of (In 1n1000)0);; see below for example.
4.2 Example: Approximate model counting of disjunctive normal forms
Given Boolean formula & of n variables in a disjunctive normal form C v C2 V... V Cm. where each clause C₁ is conjunction of literals, the DNF counting problem asks the number of truth
'The random variables (det B and det 1) share the same first and second moments, but the former does not admit efficient computation due non- conmuuammtttivity of the quaternion algebra [5).
7

---

assignments that satisfy v. denoted by c( The problem is fundamental #P-complete with applications in diverse domains ranging from network reliability to probabilistic databases (see. e.g., [21] and references therein). We next present a verifiable extension of classic Monte Carlo algorithm [16 22 Sect. 10.2] that outputs an (e, apprroxxiintoo time O(m2ne log 5-1.
Let S, be the set of truth assigments that satisfy Cj. Generate random variable W as follows: first select with probability proportional to the cardinality [ then draw an assignment a E S uniformly at random; let W ;= 1 if a does not belong to Sy for any k < j, and W == 0 otherwise. Lemma ([16). t). The mean of W equals c(bb// Σラ= |Sy] and the critical ratio is at most m.
As computing the sum of the sizes |S,] is easy, it remains to give succinct arithmetic circuit that computes W. The challenge is to turn given E random bits into a sample from the categorical distribution where the probability of (1,2...., m) is proportional to |Syl- We use rejection sampling. When the random bit string, interpreted as an integer, falls in the range spanned by the sum of [ the sample is accepted and output of the circuit is copy of W. Otherwise, the sampling fails and the circuit outputs O. The probability of failing can be made small:
Lemma 8 (f). For any 3 > O, there is an arithmetic circuit of size O (m(n + log (ogg3-1)) and degree O (mn(n + log 3)1)) such that the output of the circuit is an (0, ddeviad of W when given O(n + log 3) independent uniformly distributed bits as input.
Remark 2. If the mean of W is at most 1/2 (guaranteed, e-g.. by duplicating each clause), then the constructed random variable is also an (8, 0)-deviate of W. Namely, when the sampling of j fails, the output is O. Thus, the mean of the Bernoulli variable is at most the exact mean μ and at least
(1 - p).. The variance is at most y0( (1 - 3) nu(1 μ1) + Byr² < (1 + 8)n(1 (u) and at least (1 - () pt), implying that also the standard deviation is within relative error of most B3.
Having a circuit for W, we are ready to apply Corollary For simplicity of expressions, let us make the modest assumption that In 5-1 = (n)) or In c Ö(n). By substituting the above size and degree bounds to the formulas in the corollary, we get, after hiding logarithmic factors, that the DNF counting problem admits vras with prover time Ö(T) and verifier time Ö(VT + mn² log 8-1), where T' = (mmm)3e- d-1 (We leave the verification of these bounds to the reader.)
This example highlights some new features of our method. Since the required Monte Carlo sample size is relative small (linear in m) in comparison to the time requirement per sample (lincar in mn in the original algorithm). the verifiable extension did ineur complexity, by a factor of mn? Crucially, however, the cost of the verifier remains significantly lower than the total cost of the original algorithm. In particular, for small we have c-1 < c
negligble overhead in the total
4.3 Example: Gradient estimation
In variational inference the posterior distribution of model parameters w is approximated by a parametric distribution qww; 8) whose parameters O are optimized to maximize the objective
(0))= = E [s(w]] (L(gl)p)
where f is the log-likelihood of the data, p is a prior of w, and KT. is the Kullbac--Leible divergence [3]. A popular optimization method iteratively updates the parameters in the direction of the gradient F(), for which an approximation is obtained using a Monte Carlo method.
As concrete instantiation, consider Bayesian logistic regression 12 23 in which the probability of response y E { 1, 1, 1} given a feature vector x E R" is modeled as g (yrr-w), with g(2) = 11 +c The prior p for the parameter vector E I is taken as multivariate normal N/(0, cl) with some constant e > O, and the posterior approximation g is a multivariate normal N(4, Σ) with Σ diag(m) (1, 02 .., o.)) Thus 0 (n, Σ) and f(w) Eoswes In g(yx w), where S is the given dataset of points (xr,) which are modeled as exchangeable (i.e., independent given w).
Now, consider the estimation of the gradient of the expectation of f(w); the gradient of the KL divergence can be obtained analytically. The basic estimator is given by
N f(w f(w") Volng((w 0), w', w', ,..,................... N ~ g(w; 0).
IN ==
N
8

---

A popular variant, we omit here for simplicity, constructs the estimator based on a subsample of the data set, obtained by random sampling or by deterministically splitting the data set into batches [23]
To apply the method of trustworthy Monte Carlo, we need to find an arithmetic circuit that approx- imates random variable W [w In ((u; f), where to q(w; 0), given some number of uniformly distributed bits. In our example model, one can easily verify that the partial derivatives of In q 0) with respect to μ4; and of equal (μu - wx)/o? and [[4: - wx)² of 1/(2))) respectively. These terms being simple polynomials of wi, they can be handled in a straightforward manner, once the scalar w; has been generated, increasing the size and degree of the circuit very little. The actual challenge is to construct circuit for f(w). We next sketch a construction in four phases (details in Suppl. B). Since f(w) can be arbitrarily close (assuming exact real arithmetic). our goal is to approximate f(w) to within an absolute error > O with high probability (over the random w).
The circuit takes as input n independent and uniformly distributed bit vectors T1: .2....., I' E {0, 1]e It operates with numbers of the form k 2- where m is positive integer and k is an integer between -4th + and 4th 1 represented by 2m + 1 bits; we denote by B,, the set of these numbers. To enable exact arithmetic, m = (E)). We assume that the data values 24, ys and model parameters 0g, b4 are represented as elements of Bg. We return to the question of how to set & after the description of the four phases.
let grow the computations progress in the circuit, yet keeping
1. Sampling from the normal distribution. For each dimension 1,2,.... n, a subeircuit maps r3 to W/ E IB,, that follows approximately a (discrete) normal distribution N (Ju, of). We use finite-precision version of an algorithm that would draw exact samples if we could peform exact arithmetic with real numbers. Each subcircuit is of size and degree go(1).
2. Computing the dot product. For each data point (3c, y) E S, subcireuit maps w B to
2 =E B2m that equals yo - w. Each subcircuit is of size and degree go(1), assuming { = 2(n).
3. Evaluating the log-sigmoid. For each data point (z.z) S. a subcircuit maps the cor- responding E B2m to number Va.y E IF that approximates In g() with an absolute error most a; we let a (e))) to keep the total absolute error below e. We use cubic spline in an interval of length Olog a x-1 ") centered at O. Each subcircuit is of size O(a 1/4 log a " and degree Ollog a '); we assume m O am ")).
4. Summing over the data points. The last layer computes the sum (x.,) Vz.y- This subcircuit is of size O(SS)) and degree 1.
We argue (Suppl. B) that in phases and 2 the numbers z are generated from distribution that rapidly approaches the exact distribution as l increases. Phase 3 assumes the input numbers to have precision (aa) we achieve this by setting E, m Oloo a -)). which is Olog |S| + e)
To bound the size and degree of the circuit, assume for simplicity that [S| 2 n. Adding up the size bounds for the subcircuits yields [S](CO(1) + ((a 1og-1//11oa-11) o))) which is 0((5)5/4(1144) Multiplying the degree bounds for the four phases yields go(2), which is (log |S| + log e -1)0 We conclude, by the proof of Theorem 5 that asymptotically the prover time is Ô(T) and the verifier time is Ö(VT+ + E), where E = /5/0 and T := NE.
This example shows that we can engineer relatively succinct arithmetic circuits approximate non-polynomial functions. That said, it also shows that representing numbers as bit vectors to enable comparison (in phase 3) incurs cost that cumulates across the layers in the circuit; e.g., the dot product would require very low-degree small circuit if the arithmetic was directly over F.
5 Concluding remarks
We gave generic method for equipping Monte Carlo estimators with certificate of correctness. This method contributes towards general trustworthiness of machine learning and reasoning by enabling safe, verifiable outsourcing of sampling- based integration. When the random variables of interest can be (approximately) represented by low-degree arithmetic circuits, the method incurs only small computational overhead and the verifiers's 's work is about square root of the total work. The framework readily supports massive and simple parallelization of the computations, along with efficient error correction, with negligible additional cost 4 [4]. We used diverse set of example

---

estimators to demonstrate the technical versality of the method, with the understanding that the need for trustworthy computations may vary considerably across real application domains.
The present work being theoretical, many practical issues remain to be addressed through imple- mentation and experimentation. For example, our bounds hide polylogarithmic factors and leave room for "shaving logs" and optimizing constant factors. Another direction is to more systematically engineer building blocks needed for constructing low-degree (approximating) arithmetic circuits; we exhibited a variety of ideas and techniques, but there is a need for a "catalogue" of primitive functions and standard distributions. Finally, there are fundamental questions regarding the limitations of the method: Do random variables that result from sequential importance sampling or rejection sampling (e.g., for estimating the permanent [18] (TO) admit low-degree circuits? Can the method be extended beyond pairwise independence, for example, to Markov chain Monte Carlo?
Given the challenges in engineering low-degree circuits, it would be tempting learn succinet arithmetic circuits from examples, removing the need of human effort. Unfortunately. learning arithmetic circuits appears to be hard already for relatively restricted classes of circuits with black- box access to the function [25]; however, some interesting classes of low-depth circuits do admit efficient learning 177. Arithmetic circuits have also found their use as tractable probabilistic models. In particular, probabilistic generating circuits [2) support efficient inference and subsume related models, such as determinantal point processes (e.g.. [19]. Our work suggests that these models might serve as building blocks that readily enable extensions to efficient verifiable inference.
Acknowledgements
This research partially supported by the Academy of Finland, Grant 316771.
References
[1] Leonard Adleman, Kenneth Manders, and Gary Miller On taking roots in finite fields. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS 1977, pages 175-178. IEEE Computer Society, 1977.
[2] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES P. Ann. of Math., 160(2)7881 793, 2004.
[3] Stuart J. Berkowitz. On computing the determinant in small parallel time using small number of processors. Inf. Process. Lett., 18(3):147-155 150, 1984.
[4] Andreas Björklund and Petteri Kaski. How proofs are prepared at Camelot: Extended abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, pages 391-400. ACM, 2016.
[5] Steve Chien, Lars E. Rasmussen, and Alistair Sinclair. Clifford algebras and approximating the permanent. J. Comput. Syst. Sci., 67(2):263 2003.
[6] Rosario Gennaro, Craig Gentry, and Bryan Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers. In Advances in Cryptology CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 465-482. Springer, 2010.
[7] Christopher D. Godsil and Ivan Gutman. On the matching polynomial of a graph. In Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis János Bolyai, number 25, pages 241-249. North-Hollande 1981.
[8] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interac- tive proofs for muggles. J. ACM, 62(4):27:1-27:66 2015.
[9] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1): 11)::88-0008 1989.
[10] Juha Harviainen, Antti Röyskö, and Mikko Koivisto. Approximating the permanent with deep rejection sampling. In Advances in Neural Information Processing Systems 34, pages 213-224. Curran Associates, Inc., 2021.
10

---

[11] Wolfram Research, Inc. Mathematica, Version 13.0.0. Champaign, IL, 2021.
[12] Tommi Jaakkola and Michael I. Jordan. A variational approach to Bayesian logistic regression models and their extensions. In Proceedings of the Sixth International Workshop Artificial Intelligence and Statistics, volume RI PMLR 1997, pages 283-294. PMLR, 1997.
[13] Michael I. Jordan, Zoubin Ghahramani, Tommi S. Jaakkola, and Lawrence K. Saul. An introduction to variational methods for graphical models. Mach. Learn., 37(2):183-233) 1999.
[14] Negin Karimi, Petteri Kaski, and Mikko Koivisto. Error-correcting and verifiable parallel inference in graphical models. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI Technical Track: Reasoning under Uncertainty, pages 10194 10201. AAAI Press, 2020.
[15] 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 1993.
[16] Richard M. Karp, Michael Luby, and Neal Madras. Monte-Carlo approximation algorithms for enumeration problems. J. Algorithms, 10(3):429 448, 1989.
[17] Adam Klivans and Amir Shpilka. Learning restricted models of arithmetic circuits. Theory Comput., 2(10)) 2006.
[18] 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.
[19] Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. Found. Trends Mach. Learn., 5(2-3):123-288 2012.
[20] Ross M. McConnell, Kurt Mchlhorn, Stefan Näher, and Pascal Schweitzer. Certifying algorithms. Comput. Sci. Rev., 5(2): 19-161, 2011.
[21] Kuldeep S. Meel, Aditya A. Shrotri, and Moshe Y. Vardi. Not all FPRASs equal: Demysti- fying FPRASs for DNF-counting. Constraints An Int. J., 24(3-4):211-233 2019.
[22] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
[23] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte Carlo gradient estimation in machine learning. J. Mach. Learn. Res., 21:132:1 2020.
[24] Herbert J. Ryser. Combinatorial Mathematics, volume 14 of The Carus Mathematical Mono- graphs. Mathematical Association of America, 1963.
[25] Ilya Volkovich. A guide to learning arithmetic circuits. In Proceedings of the 29th Conference on Learning Theory, volume 49, pages 1540-1561. PMLR, 2016.
[26] Michael Walfish and Andrew J. Blumberg. Verifying computations without reexecuting them. Commun. ACM, 58(2):74-84 2015.
[27] Richard Ryan Williams. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In Proceedings of the 31st Conference on Computational Complexity, volume 50 of CCC 2016, pages 2:1-2:17. Schloss Dagstuhl Leibniz-Zentrum für Informatik. 2016.
[28] Jeannette M. Wing. Trustworthy AI. Commun. ACM, 64(10))64-71, 2021.
[29] Honghua Zhang, Brendan Juba, and Guy Van den Broeck. Probabilistic generating circuits. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of ICMI. 2021, pages 12447-12457. PMLR, 2021.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section and Section
(b) Did you describe the limitations of your work? [Yes] Limitations are discussed in Section 5.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We see no potential harm in having verifiable results.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Some of the proofs are deferred to the supplement.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or URL)? [N/A] See response to Question (c).
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] We cite Mathematica,
in accordance with its license agreement.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material [Yes] The supplemental material contains our proof-of-concep implementation of the verifiable estimator for the permanent of a matrix by Chien al. (5)
URL?
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "wa4JtcY86ez", "reviewer": "Reviewer_HG7T", "summary": "The authors study an interesting problem --- applying an algebraic proof system to certify the correctness of Monte Carlo estimators. They proposed a verifiable randomized approximation scheme based on an arithmetic circuit. Specifically, they consider both the succinct arithmetic circuit and the approximated circuit to approximate random variables. Moreover, they apply their analysis to two applications --- approximate model counting of disjunctive normal form and gradient estimation.  ", "questions": "Could the authors briefly discuss the challenges of deploying their algorithms in practice? ", "limitations": "None.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors propose a generic method to certify the correctness of Monte Carlo estimators with explicit examples. The authors fairly state the potential limitations, e.g., the lack of experiments. Though unfamiliar with this area, I think this is a welcome contribution to the trustworthy machine learning community.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "SIgmUw4hBS", "reviewer": "Reviewer_LhhL", "summary": "Monte Carlo integration methods are ubiquitous in modern computational tasks and can be highly parallelized across multiple servers. This paper introduces a framework based in algebraic circuits for verifying that the returned estimates provided by the servers were not adversarially manipulated. If the estimates were properly computed, the verification technique will not indicate the information has been manipulated. If they were not properly computed, the technique will indicate that manipulation has occurred with high probability. The authors demonstrate their technique on several classical problems, such as permanent estimation.", "questions": "Nothing additional.", "limitations": "The authors discuss the limitations of their work in the discussion section at the end of the paper. In particular, they note that it is non-obvious how to construct these verification systems for problems in which estimates do not have pairwise independence, such as MCMC or sequential inference problems. Moreover, they mention that engineering low degree circuits by hand is difficult, and that learning circuit structure is hard even for restricted problem classes.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: While this paper is mostly outside of my area of knowledge, it seems original and to have practical applications in distributed computing. A strength of the paper is the focus on examples. The examples considered are common, practical problems and illustrate the usefulness of this technique. Another strength is that the introduction clearly illustrates the motivation for the problem and provides insight into the technique being used. \n\nWeaknesses: One weakness is that the main theorem (theorem 1) feels buried in the paper. Most of the paper focuses on example problems, but it may be valuable to give a brief proof sketch of the main theorem.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QMQvA26DmOG", "reviewer": "Reviewer_xMMk", "summary": "  This paper proposes to verify Monte Carlo algorithms through the use of low-degree arithmetic circuits.\n  The idea being that if a Monte Carlo algorithm can be made to agree with a computation as represented\n  by this circuit we can be reasonably confident in the correctness of the computation after a relatively\n  small number of problem instances.\n", "questions": "What inference problems is this method best suited for?\n\nHow might one go about finding an arithmetic circuit for a particular problem?\n\nHow much additional computation should one expect on a typical example problem?", "limitations": "The authors do discuss some of the limitations of this work. Possible negative societal impacts are not discussed, but I suspect the risks are fairly minimal. The research problem being addressed is very general.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "  Originality:\n\n  While I'm not if arithmetic circuits have been used to confirm the correctness of Monte Carlo inference,\n  the idea of using multiple inference algorithms to check the correctness of each algorithm against\n  the other is not new. Many of the examples used in the paper appear to be effectively doing just that. It\n  appears the polynomial looks like a tractable expectation.\n  \n  Technical Quality:\n\n  While the paper has many examples of how these circuits could be constructed there isn't much that\n  looks like a generic method. There are no experiments or really any results showing empirically how\n  much extra time is needed to produce a correctness certificate, even for all the examples mentioned.\n  The work would greatly benefit from a more thorough exploration of some of the example circuits but\n  also a more systematic way to produce these circuits.\n  \n  Clarity:\n\n  I found the paper challenging to follow. There are many examples introduced and many extensions suggested\n  for the approach, but not much detail about the general algorithm itself.\n  \n  Significance:\n\n  I think there is much potential value in producing correctness proofs for Monte Carlo inference algorithms.\n  While it's not fully clear how often an arithmetic circuit can be found for all expectations, if that set\n  of problems can be better clarified, this could be a big deal.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NS-TrXeQYV_", "reviewer": "Reviewer_RDdx", "summary": "This paper introduces an MC integration technique in that the computations have an algebraic proof of correctness where the proof is polynomial evaluated at random points. It provides a verified randomized approximation scheme for weighed counting to approximate the target quantity by use of MC. ", "questions": "- how does it compare to others for instance [27], [8]?\n- how is pairwise independence not a very restrictive assumption in practice? \n- The performance of an MC estimator depends on the variance of the estimator. How does this method which equips MC estimators with proof correctness depend on the variance of the estimator and how would it be affected?\n -  Even though the gradient estimation for VI is interesting, however, the used estimate of the gradient is shown to have high variance. How does it work for other more advanced gradient estimators and how would the size of sub-circuits change to keep the error low? ", "limitations": "- Samples must be i.i.d. which is hard to draw in practice. \n- Lack of comparison to other techniques\n- seems choosing circuits can be difficult and begs some more discussion on that. \n- Even though some nice examples are provided it feels like it is not something widely applicable specifically for state-of-the-art methods. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- It is well-written and easy to follow. \n- Proof of this technique seems to be very standard in the literature, especially complexity theory but it is interesting to see the application in this context. \n\nWeakness: \n- Using MC requires samples to be as uncorrelated as possible to converge. This is often hard to accomplish in practice, hence MCMC. \n- There are similarities between this work and some previous work specifically [27]. \n- Some discussion on the effect of size and degree of circuits seems to be necessary.\n- Seems like finding the appropriate circuit that approximates the random variable of interest is not an easy task \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept