2024/06/28 by Lorenzo Ciardo, Ciardo, Lorenzo, Stanislav Živný +1 · 1 citation
Computer Science · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2406.19685
openalex publication_date 2024/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We connect the mixing behaviour of random walks over a graph to the power of the local-consistency algorithm for the solution of the corresponding constraint satisfaction problem (CSP). We extend this connection to arbitrary CSPs and their promise variant. In this way, we establish a linear-level (and, thus, optimal) lower bound against the local-consistency algorithm applied to the class of aperiodic promise CSPs. The proof is based on a combination of the probabilistic method for random Erdős-Rényi hypergraphs and a structural result on the number of fibers (i.e., long chains of hyperedges) in sparse hypergraphs of large girth. As a corollary, we completely classify the power of local consistency for the approximate graph homomorphism problem by establishing that, in the nontrivial cases, the problem has linear width.