{"ID":6497680,"CreatedAt":"2026-07-13T01:19:40.13847098Z","UpdatedAt":"2026-07-14T01:36:59.12045529Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.09410","arxiv_id":"2607.09410","title":"Strong Refutation of Random Ordering CSPs","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.","short_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}/\\...","url_abs":"https://arxiv.org/abs/2607.09410","url_pdf":"https://arxiv.org/pdf/2607.09410v1","authors":"[\"Xifan Yu\"]","published":"2026-07-10T13:43:24Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}