# Approximating the Permanent with Deep Rejection Sampling

arXiv: https://arxiv.org/abs/2108.07359 · HTML: https://mlsanity.com/paper/2108.07359/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2021.

## Built on by (most cited first, 2 of 2)

- [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023)
- [An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniques](https://mlsanity.com/paper/2509.13880/) (2025)

## Abstract (arXiv)

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 upper bound for the permanent 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 known to hold when every row and column has density exactly p.