Research map / Learning theory and algorithms / Combinatorial and search optimization
Satisfiability and Algorithms for Non-uniform Random k-SAT
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 a power-law degree distribution with α < k/(k−1) | Configuration Model k-SAT · Power-law degree distributions | satisfiability | Hurt |
| Reduce each clause to its two lowest-degree literals, then solve the resulting 2-SAT | Configuration Model k-SAT · Power-law degree distributions satisfying condition (2) | satisfying-assignment success | Helped |
| Use zeta-distributed degrees rather than uniform or d-regular instances | CryptoMiniSAT 5.6.6 · 3-SAT, tested across formula sizes and average degrees | explored branches | Helped |
| Increase β for zeta-distributed degrees | Configuration Model 3-SAT · n=106 and n=2·106 variables | satisfiable-formula fraction | Mixed |
| Increase β beyond approximately 2.53 | Algorithm 2 · Zeta-distributed Configuration Model 3-SAT | algorithm success probability | Helped |
Closest papers by meaning
- Analysis of Pure Literal Elimination Rule for Non-uniform Random (MAX) k-SAT Problem with an Arbitrary Degree Distribution (AAAI 2022 · similarity 0.93)
- Local Search for Hard SAT Formulas: The Strength of the Polynomial Law (AAAI 2016 · similarity 0.89)
- Parameterization of (Partial) Maximum Satisfiability above Matching in a Variable-Clause Graph (AAAI 2024 · similarity 0.87)
- DiverSAT: A Novel and Effective Local Search Algorithm for Diverse SAT Problem (AAAI 2025 · similarity 0.86)
- Solving Satisfiability Modulo Counting Exactly with Probabilistic Circuits (ICML 2025 · similarity 0.85)
- Solving Higher-Order Quantified Boolean Satisfiability via Higher-Order Model Checking (AAAI 2025 · similarity 0.85)
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.