TY - GEN

T1 - Algorithms and certificates for Boolean CSP refutation

T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022

AU - Guruswami, Venkatesan

AU - Kothari, Pravesh K.

AU - Manohar, Peter

N1 - Publisher Copyright:
© 2022 Owner/Author.

PY - 2022/9/6

Y1 - 2022/9/6

N2 - We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP with only the negation patterns of the literals re-randomized with some small probability. For an n-variable smoothed instance of a k-arity CSP, our algorithm runs in n^O(g.,") time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from 1, provided that the number of constraints is at least Õ(n) (n/ell)^(k/2-1). This matches, up to polylogarithmic factors in n, the trade-off between running time and the number of constraints of the state-of-the-art algorithms for refuting fully random instances of CSPs. We also make a surprising connection between the analysis of our refutation algorithm in the significantly "randomness starved"setting of semi-random k-XOR and the existence of even covers in worst-case hypergraphs. We use this connection to positively resolve Feige's 2008 conjecture-an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the well-known Moore bound for the girth of graphs. As a corollary, we show that polynomial-size refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the "spectral threshold"of n^(k/2), extending the celebrated result for random 3-SAT of Feige, Kim and Ofek.

AB - We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP with only the negation patterns of the literals re-randomized with some small probability. For an n-variable smoothed instance of a k-arity CSP, our algorithm runs in n^O(g.,") time, and succeeds with high probability in bounding the optimum fraction of satisfiable constraints away from 1, provided that the number of constraints is at least Õ(n) (n/ell)^(k/2-1). This matches, up to polylogarithmic factors in n, the trade-off between running time and the number of constraints of the state-of-the-art algorithms for refuting fully random instances of CSPs. We also make a surprising connection between the analysis of our refutation algorithm in the significantly "randomness starved"setting of semi-random k-XOR and the existence of even covers in worst-case hypergraphs. We use this connection to positively resolve Feige's 2008 conjecture-an extremal combinatorics conjecture on the existence of even covers in sufficiently dense hypergraphs that generalizes the well-known Moore bound for the girth of graphs. As a corollary, we show that polynomial-size refutation witnesses exist for arbitrary smoothed CSP instances with number of constraints a polynomial factor below the "spectral threshold"of n^(k/2), extending the celebrated result for random 3-SAT of Feige, Kim and Ofek.

KW - CSP refutation

KW - Even covers

KW - Smoothed CSPs

UR - http://www.scopus.com/inward/record.url?scp=85132739999&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132739999&partnerID=8YFLogxK

U2 - 10.1145/3519935.3519955

DO - 10.1145/3519935.3519955

M3 - Conference contribution

AN - SCOPUS:85132739999

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 678

EP - 689

BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Leonardi, Stefano

A2 - Gupta, Anupam

PB - Association for Computing Machinery

Y2 - 20 June 2022 through 24 June 2022

ER -