# Solving Marginal MAP Problems with NP Oracles and Parity Constraints

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2016.

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

- [A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models](https://mlsanity.com/paper/2303.15626/) (2023)
- [Efficient and Reliable Probabilistic Interactive Learning with Structured Outputs](https://mlsanity.com/paper/2202.08566/) (2022)
- [Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees](https://mlsanity.com/paper/2309.08883/) (2023)
- [Trading off Consistency and Dimensionality of Convex Surrogates for the Mode](https://mlsanity.com/paper/2402.10818/) (2024)
- [Provable Constrained Stochastic Convex Optimization with XOR-Projected Gradient Descent](https://mlsanity.com/paper/2203.11829/) (2022)

## Abstract (arXiv)

Arising from many applications at the intersection of decision making and machine learning, Marginal Maximum A Posteriori (Marginal MAP) Problems unify the two main classes of inference, namely maximization (optimization) and marginal inference (counting), and are believed to have higher complexity than both of them. We propose XOR_MMAP, a novel approach to solve the Marginal MAP Problem, which represents the intractable counting subproblem with queries to NP oracles, subject to additional parity constraints. XOR_MMAP provides a constant factor approximation to the Marginal MAP Problem, by encoding it as a single optimization in polynomial size of the original problem. We evaluate our approach in several machine learning and decision making applications, and show that our approach outperforms several state-of-the-art Marginal MAP solvers.