Strong Refutation of Random Ordering CSPs
2026-07-10 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Complexity
AI summaryⓘ
The authors study how to prove that certain random ordering problems have no solutions, using efficient algorithms. They provide a method that works well when there are enough constraints, depending on a property called the coordinate degree of the problem. They also describe how the running time, the number of constraints, and the strength of the proof are related in a balanced way. Finally, they show that their approach is likely close to the best possible by proving limits on similar algorithms.
ordering constraint satisfaction problemsrandom CSPrefutation algorithmcoordinate degreeclause densityKikuchi methodpolynomial-time algorithmscomputational lower boundstradeoff analysis
Authors
Xifan Yu
Abstract
In this work, we initiate the study of strongly refuting the satisfiability of random ordering constraint satisfaction problems. We show that there is a polynomial-time $\varepsilon$-refutation algorithm for random ordering CSP with predicate $P$ when the number of clauses is above the threshold $\tildeΩ\left(n^{d/2}/\varepsilon^2\right)$, where $d$ is the coordinate degree of the predicate $P$. We further give a smooth three-way tradeoff between the running time, the clause density, and the refutation strength $\varepsilon$ using the Kikuchi method. Finally, we complement our algorithmic results with a computational lower bound based on the class of low coordinate degree algorithms, providing evidence that the established three-way tradeoff is near optimal.