Research map / Graph learning / Graph algorithms and clustering
MixSATGEN: Learning Graph Mixing for SAT Instance Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MixSATGEN, a method for generating hard SAT instances by learning graph mixing of existing instances, aimed at producing plausible-hardness instances for tuning SAT solvers.
Problem
Generating hard, realistic SAT instances is needed because real-world SAT instances are scarce and useful for tuning solvers; existing methods either fail to keep plausible hardness or have limited applicability.
Approach
Instead of construction-based generation, learns to mix graph structures of existing SAT instances (graph mixing) to produce new instances that retain plausible hardness.
Closest papers by meaning
- G2SAT: Learning to Generate SAT Formulas (NeurIPS 2019 · similarity 0.91)
- On the Expressive Power of GNNs for Boolean Satisfiability (ICLR 2026 · similarity 0.90)
- SAT-Based Tree Decomposition with Iterative Cascading Policy Selection (AAAI 2024 · similarity 0.88)
- Parameterization of (Partial) Maximum Satisfiability above Matching in a Variable-Clause Graph (AAAI 2024 · similarity 0.87)
- HardCore Generation: Generating Hard UNSAT Problems for Data Augmentation (NeurIPS 2024 · similarity 0.87)
- Learning How to Cube (NeurIPS 2026 · similarity 0.87)
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.