• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
On the Usefulness of Linear Modular Arithmetic in Constraint Programming.
Gilles Pesant, Kuldeep S. Meel and Mahshid Mohammadalitajrishi.
In Proceedings of International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), July 2021.
Linear modular constraints are a powerful class of constraints that arise naturally in cryptanalysis, checksums, hash functions, and the like. Given their importance, the past few years have witnessed the design of combinatorial solvers with native support for linear modular constraints, and the availability of such solvers has led to the emergence of new applications. While there exist global constraints inCPthat consider congruence classes over domain values,linear modular arithmetic constraints have yet to appear in the global constraint catalogue despite their past investigation in the context of model counting for CSPs. In this work we seek to remedy the situation by advocating the integrationof linear modular constraints in state-of-the-ar tCP solvers.Contrary to previous belief, we conclude from an empirical investigation that Gauss-Jordan Elimination based techniques can provide an efficient and scalable way to handle linear modular constraints. On the theoretical side, we remark onthe pairwise independence offered by hash functions based on linear modular constraints, and then discuss the design of hashing-based model counters for CP,supported by empirical results showing the accuracy and computational savings that can be achieved. We further demonstrate the usefulness of native support for linear modular constraints with applications to checksums and model counting
@inproceedings{PMM21,
title={ On the Usefulness of Linear Modular Arithmetic in Constraint Programming},
author={Pesant, Gilles and Meel, Kuldeep S. and Mohammadalitajrishi, Mahshid},
booktitle=CPAIOR,
bib2html_pubtype={Refereed Conference},
year={2021},
month=jul,
bib2html_rescat={Counting},
bib2html_dl_pdf={../Papers/cpaior21-pmm.pdf},
abstract={Linear modular constraints are a powerful class of constraints that arise naturally in cryptanalysis, checksums, hash functions, and the like. Given their importance, the past few years have witnessed the design of combinatorial solvers with native support for linear modular constraints, and the availability of such solvers has led to the emergence of new applications. While there exist global constraints inCPthat consider congruence classes over domain values,linear modular arithmetic constraints have yet to appear in the global constraint catalogue despite their past investigation in the context of model counting for CSPs. In this work we seek to remedy the situation by advocating the integrationof linear modular constraints in state-of-the-ar tCP solvers.Contrary to previous belief, we conclude from an empirical investigation that Gauss-Jordan Elimination based techniques can provide an efficient and scalable way to handle linear modular constraints. On the theoretical side, we remark onthe pairwise independence offered by hash functions based on linear modular constraints, and then discuss the design of hashing-based model counters for CP,supported by empirical results showing the accuracy and computational savings that can be achieved. We further demonstrate the usefulness of native support for linear modular constraints with applications to checksums and model counting},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sun Apr 14, 2024 11:15:51