2026-08-10T19:43:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23698 2025-10-27T10:42:32Z ddc:004 open_access

Hardness of Clique Approximation for Monotone Circuits Błasiok, Jarosław Meierhöfer, Linus circuit lower bounds monotone circuits sunflower conjecture We consider a problem of approximating the size of the largest clique in a graph, using a monotone circuit. Concretely, we focus on distinguishing a random Erdős–Rényi graph 𝒢_{n,p}, with p = n^{-2/(α-1)} chosen st. with high probability it does not even contain an α-clique, from a random clique on β vertices (where α ≤ β). Using the approximation method of Razborov, Alon and Boppana showed in their influential work in 1987 that as long as √{α} β < n^{1-δ}/log n, this problem requires a monotone circuit of size n^Ω(δ√α), implying a lower bound of 2^Ω̃(n^{1/3}) for the exact version of the problem Clique_k when k≈ n^{2/3}. Recently, Cavalar, Kumar, and Rossman improved their result by showing a tight lower bound n^Ω(k), in a limited range k ≤ n^{1/3}, implying a comparable 2^Ω̃(n^{1/3}) lower bound after choosing the largest admissible k. We combine the ideas of Cavalar, Kumar and Rossman with recent breakthrough results on sunflower conjecture by Alweiss, Lovett, Wu, and Zhang to show that as long as α β < n^{1-δ}/log n, any monotone circuit rejecting 𝒢_{n,p} graph while accepting a β-clique needs to have size at least n^Ω(δ²α); this implies a stronger 2^Ω̃(√n) lower bound for the unrestricted version of the problem. We complement this result with a construction of an explicit monotone circuit of size O(n^{δ² α/2}) which rejects 𝒢_{n,p}, and accepts any graph containing β-clique whenever β > n^{1-δ}. In particular, those two theorems give a precise characterization of the smallest β-clique that can be distinguished from 𝒢_{n, 1/2}: when β > n / 2^{C √{log n}}, there is a polynomial-size circuit that solves it, while for β < n / 2^ω(√{log n}) every circuit needs size n^ω(1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jarosław Błasiok and Linus Meierhöfer 2025 Is Part Of LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2025.4 urn:nbn:de:0030-drops-236987 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode