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 - https://www.scopus.com/pages/publications/85139121623
UR - https://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 -