TrustworthyMonteCarlo

Wepresent an orchestration of the computations such that theoutcome isaccompanied withaproofofcorrectness thatcanbeverifiedwith substantially less computational resources than it takes to run the computations fromscratch withstate-of-the-art algorithms. Specifically,weadopt analgebraic proof system developed incomputational complexity theory,inwhich theproof is represented by a polynomial; evaluating the polynomial at a random point amounts to a verification of the proof with probabilistic guarantees.