Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

DOI10.1145/3519935.3519955arXiv2109.04415OpenAlexW3196550748MaRDI QIDQ6083522

Peter Manohar, Venkatesan Guruswami, Pravesh K. Kothari

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.04415

zbMATH Keywords

even coversCSP refutationsmoothed CSPs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random