TY - GEN

T1 - Bypassing the XOR Trick

T2 - 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022

AU - Guruswami, Venkatesan

AU - Kothari, Pravesh K.

AU - Manohar, Peter

N1 - Publisher Copyright:
© Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar.

PY - 2022/9/1

Y1 - 2022/9/1

N2 - Let H(k, n, p) be the distribution on k-uniform hypergraphs where every subset of [n] of size k is included as an hyperedge with probability p independently. In this work, we design and analyze a simple spectral algorithm that certifies a bound on the size of the largest clique, ω(H), in hypergraphs H ∼ H(k, n, p). For example, for any constant p, with high probability over the choice of the hypergraph, our spectral algorithm certifies a bound of Õ(√n) on the clique number in polynomial time. This matches, up to polylog(n) factors, the best known certificate for the clique number in random graphs, which is the special case of k = 2. Prior to our work, the best known refutation algorithms [4, 1] rely on a reduction to the problem of refuting random k-XOR via Feige's XOR trick [6], and yield a polynomially worse bound of Õ(n3/4) on the clique number when p = O(1). Our algorithm bypasses the XOR trick and relies instead on a natural generalization of the Lovász theta semidefinite programming relaxation for cliques in hypergraphs.

AB - Let H(k, n, p) be the distribution on k-uniform hypergraphs where every subset of [n] of size k is included as an hyperedge with probability p independently. In this work, we design and analyze a simple spectral algorithm that certifies a bound on the size of the largest clique, ω(H), in hypergraphs H ∼ H(k, n, p). For example, for any constant p, with high probability over the choice of the hypergraph, our spectral algorithm certifies a bound of Õ(√n) on the clique number in polynomial time. This matches, up to polylog(n) factors, the best known certificate for the clique number in random graphs, which is the special case of k = 2. Prior to our work, the best known refutation algorithms [4, 1] rely on a reduction to the problem of refuting random k-XOR via Feige's XOR trick [6], and yield a polynomially worse bound of Õ(n3/4) on the clique number when p = O(1). Our algorithm bypasses the XOR trick and relies instead on a natural generalization of the Lovász theta semidefinite programming relaxation for cliques in hypergraphs.

KW - Average-case complexity

KW - Planted clique

KW - Random matrix theory

KW - Spectral refutation

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

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

U2 - 10.4230/LIPIcs.APPROX/RANDOM.2022.42

DO - 10.4230/LIPIcs.APPROX/RANDOM.2022.42

M3 - Conference contribution

AN - SCOPUS:85139121623

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022

A2 - Chakrabarti, Amit

A2 - Swamy, Chaitanya

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 19 September 2022 through 21 September 2022

ER -