# The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 77 references that are in the map.
- First posted on arXiv 3 Jun 2021.

## Builds on (most cited first, 20 of 20)

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent](https://mlsanity.com/paper/2009.06107/) (2020)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Computational Hardness of Certifying Bounds on Constrained PCA Problems](https://mlsanity.com/paper/1902.07324/) (2019)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013)
- [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018)
- [Optimal Low-Degree Hardness of Maximum Independent Set](https://mlsanity.com/paper/2010.06563/) (2020)
- [Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond](https://mlsanity.com/paper/1912.11071/) (2019)
- [Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs](https://mlsanity.com/paper/2008.12237/) (2020)
- [Local algorithms for independent sets are half-optimal](https://mlsanity.com/paper/1402.0485/) (2014)
- [The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property](https://mlsanity.com/paper/1904.07174/) (2019)
- [Optimization of Mean-field Spin Glasses](https://mlsanity.com/paper/2001.00904/) (2020)
- [Free Energy Wells and Overlap Gap Property in Sparse PCA](https://mlsanity.com/paper/2006.10689/) (2020)
- [Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem](https://mlsanity.com/paper/1402.0052/) (2014)
- [Analysing Survey Propagation Guided Decimation on Random Formulas](https://mlsanity.com/paper/1602.08519/) (2016)

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

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Reconstruction on Trees and Low-Degree Polynomials](https://mlsanity.com/paper/2109.06915/) (2021)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [SQ Lower Bounds for Random Sparse Planted Vector Problem](https://mlsanity.com/paper/2301.11124/) (2023)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems](https://mlsanity.com/paper/2603.20589/) (2026)
- [Quantum-Inspired Approximations to Constraint Satisfaction Problems](https://mlsanity.com/paper/2212.04016/) (2022)
- [Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)](https://mlsanity.com/paper/2411.10453/) (2024)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)
- [A Smooth Computational Transition in Tensor PCA](https://mlsanity.com/paper/2509.09904/) (2025)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## Abstract (arXiv)

Let Phi be a uniformly random k-SAT formula with n variables and m clauses. We study the algorithmic task of finding a satisfying assignment of Phi. It is known that satisfying assignments exist with high probability up to clause density m/n = 2k log 2 - frac12 (log 2 + 1) + ok(1), while the best polynomial-time algorithm known, the Fix algorithm of Coja-Oghlan, finds a satisfying assignment at the much lower clause density (1 - ok(1)) 2k log k / k. This prompts the question: is it possible to efficiently find a satisfying assignment at higher clause densities? We prove that the class of low degree polynomial algorithms cannot find a satisfying assignment at clause density (1 + ok(1)) kappa^* 2k log k / k for a universal constant kappa^* ≈ 4.911. This class encompasses Fix, message passing algorithms including Belief and Survey Propagation guided decimation (with bounded or mildly growing number of rounds), and local algorithms on the factor graph. This is the first hardness result for any class of algorithms at clause density within a constant factor of that achieved by Fix. Our proof establishes and leverages a new many-way overlap gap property tailored to random k-SAT.