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{\Omega}\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.