# Learning from Survey Propagation: a Neural Network for MAX-E-3-SAT

arXiv: https://arxiv.org/abs/2012.06344 · HTML: https://mlsanity.com/paper/2012.06344/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2020.

## Built on by (most cited first, 11 of 11)

- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Phase transitions in the mini-batch size for sparse and dense two-layer neural networks](https://mlsanity.com/paper/2305.06435/) (2023)
- [Stable Attractors for Neural networks classification via Ordinary Differential Equations (SA-nODE)](https://mlsanity.com/paper/2311.10387/) (2023)
- [Complex Recurrent Spectral Network](https://mlsanity.com/paper/2312.07296/) (2023)
- [Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems](https://mlsanity.com/paper/2309.05337/) (2023)
- [torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem](https://mlsanity.com/paper/2402.03640/) (2024)
- [Fast Analysis of the OpenAI O1-Preview Model in Solving Random K-SAT Problem: Does the LLM Solve the Problem Itself or Call an External SAT Solver?](https://mlsanity.com/paper/2409.11232/) (2024)
- [Application of AI to formal methods - an analysis of current trends](https://mlsanity.com/paper/2411.14870/) (2024)
- [Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems](https://mlsanity.com/paper/2602.18419/) (2026)
- [Engineered Ordinary Differential Equations as Classification Algorithm (EODECA): thorough characterization and testing](https://mlsanity.com/paper/2312.14681/) (2023)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)

## Abstract (arXiv)

Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algorithm for computing approximate solutions in Theta(N) for the Maximum Exact 3-Satisfiability (MAX-E-3-SAT) problem by using deep learning methodology. This methodology allows us to create a learning algorithm able to fix Boolean variables by using local information obtained by the Survey Propagation algorithm. By performing an accurate analysis, on random CNF instances of the MAX-E-3-SAT with several Boolean variables, we show that this new algorithm, avoiding any decimation strategy, can build assignments better than a random one, even if the convergence of the messages is not found. Although this algorithm is not competitive with state-of-the-art Maximum Satisfiability (MAX-SAT) solvers, it can solve substantially larger and more complicated problems than it ever saw during training.