Research map / Learning theory and algorithms / Combinatorial and search optimization
The Expressive Power of Ad-Hoc Constraints for Modelling CSPs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 BCT instead of OMVD to encode fixed-treewidth CSPs | Ad-hoc constraint representation · F14: CSPs with fixed treewidth | polysize encodability | Helped |
| Use CFG instead of BCT to encode F15 | Ad-hoc constraint representation · F15: mirrored-string constraint family | polysize encodability | Helped |
| Use BCT instead of smaT for conjunction | Ad-hoc constraint operations · Conjunction of constraints | tractability | Helped |
| Use BCT instead of smaT for forgetting variables | Ad-hoc constraint operations · Forgetting (FO) | tractability | Helped |
| Use sMDD instead of OMDD for sentential entailment | Ad-hoc constraint queries · Sentential entailment | tractability | Hurt |
| Use table instead of shoT for validity queries | Ad-hoc constraint queries · Validity | tractability | Helped |
Closest papers by meaning
- On the Modelling of Constraints with Tractable Logical Operators (AAAI 2025 · similarity 0.90)
- Encoding Constraints as Binary Constraint Networks Satisfying BTP (AAAI 2024 · similarity 0.87)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.85)
- Exploiting Symmetries in MUS Computation (AAAI 2025 · similarity 0.85)
- On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? (AAAI 2024 · similarity 0.84)
- An Eager Satisfiability Modulo Theories Solver for Algebraic Datatypes (AAAI 2024 · similarity 0.83)
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.