Research map / Learning theory and algorithms / Prediction and decision losses
SAT Encodings for Distance-Based Belief Merging Operators
Sébastien Konieczny, Jean-Marie Lagniez, Pierre Marquis
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use sum aggregator instead of GMin/GMax | encoding computation · Time-tabling merging, 15 bases | compilation time (s): 260.34 ± 284.1 -> 1.37 ± 1.9 | Improved |
| use GMax instead of GMin aggregator (D distance) | encoding computation · Time-tabling merging, 15 bases | instances solved of 25: 10 -> 17 | Improved |
| use GMax instead of GMin aggregator (H distance) | encoding computation · Time-tabling merging, 15 bases | instances solved of 25: 8 -> 18 | Improved |
| increase number of bases in profile from 5 to 15 | D-Sum encoding · Time-tabling merging | compilation time (s): 0.65 ± 0.3 -> 1.37 ± 1.9 | Hurt |
| increase number of bases in profile from 5 to 15 | D-GMin encoding · Time-tabling merging | instances solved of 25: 25 -> 10 | Hurt |
| increase time-out from 900s to 3600s | D-GMax encoding · Time-tabling merging, 150 instances | instances solved of 150 | Improved |
| increase time-out from 900s to 3600s | D-GMin encoding · Time-tabling merging, 150 instances | instances solved of 150 | Improved |
| use Hamming instead of drastic distance | Sum encoding · Time-tabling merging, 15 bases | compilation time (s): 1.37 ± 1.9 -> 21.634 ± 43.5 | Hurt |
| use SAT-based encoding instead of OBDD compilation | distance-based merging · Time-tabling merging, 150 instances | OBDD compile success | Improved |
Closest papers by meaning
- NSNet: A General Neural Probabilistic Framework for Satisfiability Problems (NeurIPS 2022 · similarity 0.84)
- Hardness of Random Reordered Encodings of Parity for Resolution and CDCL (AAAI 2024 · similarity 0.82)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.82)
- Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning (ICLR 2025 · similarity 0.81)
- Scaling Up, Speeding Up: A Benchmark of Speculative Decoding for Efficient LLM Test-Time Scaling (ICLR 2026 · similarity 0.81)
- TriAttention: Efficient Long Reasoning with Trigonometric KV Compression (ICML 2026 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
