Optimization With Parity Constraints: From Binary Codes to Discrete Integration

Stefano Ermon, Carla Gomes, Ashish Sabharwal, Bart Selman
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:95-104, 2013.

Abstract

Many probabilistic inference tasks involve summations over exponentially large sets. Recently, it has been shown that these problems can be reduced to solving a polynomial number of MAP inference queries for a model augmented with randomly generated parity constraints. By exploiting a connection with max-likelihood decoding of binary codes, we show that these optimizations are computationally hard. Inspired by iterative message passing decoding algorithms, we propose an Integer Linear Programming (ILP) formulation for the problem, enhanced with new sparsification techniques to improve decoding performance. By solving the ILP through a sequence of LP relaxations, we get both lower and upper bounds on the partition function, which hold with high probability and are much tighter than those obtained with variational methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-ermon13a, title = {Optimization With Parity Constraints: From Binary Codes to Discrete Integration}, author = {Ermon, Stefano and Gomes, Carla and Sabharwal, Ashish and Selman, Bart}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {95--104}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/ermon13a/ermon13a.pdf}, url = {https://proceedings.mlr.press/r11/ermon13a.html}, abstract = {Many probabilistic inference tasks involve summations over exponentially large sets. Recently, it has been shown that these problems can be reduced to solving a polynomial number of MAP inference queries for a model augmented with randomly generated parity constraints. By exploiting a connection with max-likelihood decoding of binary codes, we show that these optimizations are computationally hard. Inspired by iterative message passing decoding algorithms, we propose an Integer Linear Programming (ILP) formulation for the problem, enhanced with new sparsification techniques to improve decoding performance. By solving the ILP through a sequence of LP relaxations, we get both lower and upper bounds on the partition function, which hold with high probability and are much tighter than those obtained with variational methods.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Optimization With Parity Constraints: From Binary Codes to Discrete Integration %A Stefano Ermon %A Carla Gomes %A Ashish Sabharwal %A Bart Selman %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-ermon13a %I PMLR %P 95--104 %U https://proceedings.mlr.press/r11/ermon13a.html %V R11 %X Many probabilistic inference tasks involve summations over exponentially large sets. Recently, it has been shown that these problems can be reduced to solving a polynomial number of MAP inference queries for a model augmented with randomly generated parity constraints. By exploiting a connection with max-likelihood decoding of binary codes, we show that these optimizations are computationally hard. Inspired by iterative message passing decoding algorithms, we propose an Integer Linear Programming (ILP) formulation for the problem, enhanced with new sparsification techniques to improve decoding performance. By solving the ILP through a sequence of LP relaxations, we get both lower and upper bounds on the partition function, which hold with high probability and are much tighter than those obtained with variational methods. %Z Reissued by PMLR on 04 October 2026.
APA
Ermon, S., Gomes, C., Sabharwal, A. & Selman, B.. (2013). Optimization With Parity Constraints: From Binary Codes to Discrete Integration. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:95-104 Available from https://proceedings.mlr.press/r11/ermon13a.html. Reissued by PMLR on 04 October 2026.

Related Material