Research map / Learning theory and algorithms / Matrix and tensor methods
Approximating the Permanent by Sampling from Adaptive Partitions
Jonathan Kuck, Tri Dao, Hamid Rezatofighi, Ashish Sabharwal, Stefano Ermon
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AdaPart instead of fixed partitioning | Permanent sampling on real-world network matrices · ENZYMES-g192, ENZYMES-g230, ENZYMES-g479, and bcspwr01 | runtime: 4.2 vs 52.9; 3.3 vs 55.5; 1.8 vs 45.1; 4.2 vs 74.8 sec. | Improved |
| Use AdaPart instead of fixed partitioning | Permanent sampling on cage5 · cage5 | runtime: 6.1 sec. vs TIMEOUT | Improved |
| Use the optimal proposal distribution sampled by AdaPart instead of sequential proposals or MHT hypotheses | Rao-Blackwellized particle filtering for multi-target tracking · Synthetic tracking with 10 targets | maximum association log-likelihood: an order of magnitude fewer samples | Improved |
| Use the optimal proposal distribution sampled by AdaPart instead of sequential proposals or MHT hypotheses | Rao-Blackwellized particle filtering for multi-target tracking · Synthetic tracking with 10 targets | mean squared error: an order of magnitude fewer samples | Improved |
| Tighten upper bounds whenever slack is encountered (ablation) | AdaPart · Uniform random matrices, sizes 10, 15, and 25 | upper bound relative to original: 64%, 77%, and 89% of the original bound | Improved |
| Tighten upper bounds whenever slack is encountered (ablation) | AdaPart · ENZYMES-g192, ENZYMES-g230, ENZYMES-g479, cage5, and bcspwr01 | upper bound relative to original: 25%, 22%, 8%, 7%, and 19% | Improved |
Closest papers by meaning
- A Faster Practical Approximation Scheme for the Permanent (AAAI 2023 · similarity 0.87)
- Estimating the Permanent by Nesting Importance Sampling (ICML 2024 · similarity 0.85)
- Sampling in Unit Time with Kernel Fisher-Rao Flow (ICML 2024 · similarity 0.84)
- Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers (ICLR 2024 · similarity 0.83)
- To discretize continually: Mean shift interacting particle systems for Bayesian inference (NeurIPS 2026 · similarity 0.83)
- Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
