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 prob- lems can be reduced to solving a polyno- mial number of MAP inference queries for a model augmented with randomly gener- ated parity constraints. By exploiting a con- nection with max-likelihood decoding of bi- nary codes, we show that these optimizations are computationally hard. Inspired by iter- ative 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 parti- tion function, which hold with high probabil- ity 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 prob- lems can be reduced to solving a polyno- mial number of MAP inference queries for a model augmented with randomly gener- ated parity constraints. By exploiting a con- nection with max-likelihood decoding of bi- nary codes, we show that these optimizations are computationally hard. Inspired by iter- ative 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 parti- tion function, which hold with high probabil- ity 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 prob- lems can be reduced to solving a polyno- mial number of MAP inference queries for a model augmented with randomly gener- ated parity constraints. By exploiting a con- nection with max-likelihood decoding of bi- nary codes, we show that these optimizations are computationally hard. Inspired by iter- ative 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 parti- tion function, which hold with high probabil- ity 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