56 citations · 118 across the 19 of their papers we have counts for
14 papers · 1 filter
Approximating the Permanent with Deep Rejection Sampling
Juha Harviainen, Antti Röyskö, Mikko Koivisto
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…
Fast Multi-Subset Transform and Weighted Sums Over Acyclic Digraphs
Mikko Koivisto, Antti Röyskö
The zeta and Moebius transforms over the subset lattice of elements and the so-called subset convolution are examples of unary and binary operations on set functions. While the…
Dense Subset Sum may be the hardest
Per Austrin, Mikko Koivisto, Petteri Kaski +1
The Subset Sum problem asks whether a given set of positive integers contains a subset of elements that sum up to a given target . It is an outstanding open question whether…
Treedy: A Heuristic for Counting and Sampling Subsets
Teppo Niinimaki, Mikko Koivisto
Consider a collection of weighted subsets of a ground set N. Given a query subset Q of N, how fast can one (1) find the weighted sum over all subsets of Q, and (2) sample a subset…
Space--Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
Per Austrin, Petteri Kaski, Mikko Koivisto +1
The technique of Schroeppel and Shamir (SICOMP, 1981) has long been the most efficient way to trade space against time for the SUBSET SUM problem. In the random-instance setting, h…
On Finding Optimal Polytrees
Serge Gaspers, Mikko Koivisto, Mathieu Liedloff +2
Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to pol…