File MonteCarlo.h

↰ Parent directory (ADS/algorithm)

Monte Carlo algorithms of chapter 17, quick and wrong with a bounded probability, which K independent runs lower to its K-th power:

Definition (`ADS/algorithm/MonteCarlo.h`)

zeroPolynomial(), whether a polynomial of total degree d, given as a function of its n variables, is identically 0: by the lemma of Schwartz and Zippel a random point of { 1 , … , 2 d }^n is a root of a nonzero one with probability at most 1/2; “zero” may be wrong, “not zero” never;
freivalds(), whether A B = C for n x n matrices: A ( B x ) against C x for a random x of +1 and -1, O( n^2 ) per run instead of the product, wrong with probability at most 1/2 when A B != C (exercise 17.4);
halfSatisfiable(), whether a boolean formula of n variables is true on more than half of the assignments, from the fraction of the true ones among K random assignments (exercise 17.5): by the bound of Hoeffding it errs with probability at most :math:` e^{-2 K epsilon^2} ` when the true fraction is 1/2 + epsilon or 1/2 - epsilon.

The contracts [see File Contract.h]: K >= 0 repetitions, and freivalds() needs three n x n matrices. The functions are defined in MonteCarlo.tpp.

Montresor, Algoritmi e Strutture Dati, 2025, chapter 17 and exercises 17.4 and 17.5, https://algoritmicamente.it/materiali/libro/capitoli/cap17.pdf

1. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, Journal of the ACM 27(4), 701-717, 1980, doi:10.1145/322217.322225

Zippel, Probabilistic algorithms for sparse polynomials, EUROSAM 1979, LNCS 72, 216-226, 1979, doi:10.1007/3-540-09519-5_73

Freivalds, Probabilistic machines can use less running time, IFIP Congress 1977, 839-842

Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58(301), 13-30, 1963, doi:10.1080/01621459.1963.10500830

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli