Timezone: »

Approximating the Permanent with Deep Rejection Sampling
Juha Harviainen · Antti Röyskö · Mikko Koivisto

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
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$.

Author Information

Juha Harviainen (University of Helsinki)
Antti Röyskö (Swiss Federal Institute of Technology)
Mikko Koivisto (Helsinki Institute for Information Technology)

More from the Same Authors

  • 2022 Poster: Trustworthy Monte Carlo »
    Juha Harviainen · Mikko Koivisto · Petteri Kaski
  • 2022 Spotlight: Lightning Talks 2A-2 »
    Harikrishnan N B · Jianhao Ding · Juha Harviainen · Yizhen Wang · Lue Tao · Oren Mangoubi · Tong Bu · Nisheeth Vishnoi · Mohannad Alhanahnah · Mikko Koivisto · Aditi Kathpalia · Lei Feng · Nithin Nagaraj · Hongxin Wei · Xiaozhu Meng · Petteri Kaski · Zhaofei Yu · Tiejun Huang · Ke Wang · Jinfeng Yi · Jian Liu · Sheng-Jun Huang · Mihai Christodorescu · Songcan Chen · Somesh Jha
  • 2022 Spotlight: Trustworthy Monte Carlo »
    Juha Harviainen · Mikko Koivisto · Petteri Kaski
  • 2014 Poster: Learning Chordal Markov Networks by Dynamic Programming »
    Kustaa Kangas · Mikko Koivisto · Teppo Niinimäki