# Hard Optimization Problems have Soft Edges

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2022.

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

- [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)
- [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)
- [Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis](https://mlsanity.com/paper/2512.03419/) (2025)

## Abstract (arXiv)

Finding a Maximum Clique is a classic property test from graph theory; find any one of the largest complete subgraphs in an Erd"os-R'enyi G(N, p) random graph. We use Maximum Clique to explore the structure of the problem as a function of N, the graph size, and K, the clique size sought. It displays a complex phase boundary, a staircase of steps at each of which 2log2 N and Kmax, the maximum size of a clique that can be found, increases by 1. Each of its boundaries has a finite width, and these widths allow local algorithms to find cliques beyond the limits defined by the study of infinite systems. We explore the performance of a number of extensions of traditional fast local algorithms, and find that much of the "hard" space remains accessible at finite N. The "hidden clique" problem embeds a clique somewhat larger than those which occur naturally in a G(N, p) random graph. Since such a clique is unique, we find that local searches which stop early, once evidence for the hidden clique is found, may outperform the best message passing or spectral algorithms.