# Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2013.

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

- [Partition Function Estimation: A Quantitative Study](https://mlsanity.com/paper/2105.11132/) (2021)
- [Rounding Meets Approximate Model Counting](https://mlsanity.com/paper/2305.09247/) (2023)
- [X-MEN: Guaranteed XOR-Maximum Entropy Constrained Inverse Reinforcement Learning](https://mlsanity.com/paper/2203.11842/) (2022)
- [Solution Enumeration by Optimality in Answer Set Programming](https://mlsanity.com/paper/2108.03474/) (2021)
- [Projected Model Counting: Beyond Independent Support](https://mlsanity.com/paper/2110.09171/) (2021)
- [Dynamic Range Reduction via Branch-and-Bound](https://mlsanity.com/paper/2409.10863/) (2024)
- [Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees](https://mlsanity.com/paper/2309.08883/) (2023)
- [Formally Certified Approximate Model Counting](https://mlsanity.com/paper/2406.11414/) (2024)
- [The application of Evolutionary and Nature Inspired Algorithms in Data Science and Data Analytics](https://mlsanity.com/paper/2202.03859/) (2022)
- [Provable Constrained Stochastic Convex Optimization with XOR-Projected Gradient Descent](https://mlsanity.com/paper/2203.11829/) (2022)
- [Learning Markov Random Fields for Combinatorial Structures via Sampling through Lov'asz Local Lemma](https://mlsanity.com/paper/2212.00296/) (2022)
- [Systematic Parameter Decision in Approximate Model Counting](https://mlsanity.com/paper/2504.05874/) (2025)

## Abstract (arXiv)

Integration is affected by the curse of dimensionality and quickly becomes intractable as the dimensionality of the problem grows. We propose a randomized algorithm that, with high probability, gives a constant-factor approximation of a general discrete integral defined over an exponentially large set. This algorithm relies on solving only a small number of instances of a discrete combinatorial optimization problem subject to randomly generated parity constraints used as a hash function. As an application, we demonstrate that with a small number of MAP queries we can efficiently approximate the partition function of discrete graphical models, which can in turn be used, for instance, for marginal computation or model selection.