2026-08-16T21:51:48Z https://drops.dagstuhl.de/oai

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

Lifting with Colourful Sunflowers de Rezende, Susanna F. Vinyals, Marc lifting sunflower clique colouring monotone circuit cutting planes We show that a generalization of the DAG-like query-to-communication lifting theorem, when proven using sunflowers over non-binary alphabets, yields lower bounds on the monotone circuit complexity and proof complexity of natural functions and formulas that are better than previously known results obtained using the approximation method. These include an n^Ω(k) lower bound for the clique function up to k ≤ n^{1/2-ε}, and an exp(Ω(n^{1/3-ε})) lower bound for a function in P. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Susanna F. de Rezende and Marc Vinyals 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.36 urn:nbn:de:0030-drops-237303 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.36 eng https://creativecommons.org/licenses/by/4.0/legalcode