The periodic structure of local consistency
<|reference_start|>The periodic structure of local consistency: 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\H{o}s-R\'enyi 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.<|reference_end|>
@article{ciardo2024the,
    title={The periodic structure of local consistency},
    author={Lorenzo Ciardo and Stanislav v{Z}ivn'y},
    journal={arXiv preprint arXiv:2406.19685},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.19685},
    primaryClass={cs.CC cs.DM cs.DS}
}