Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Lifting with colourful sunflowers

de Rezende, Susanna F. LU orcid and Vinyals, Marc (2025) 40th Computational Complexity Conference, CCC 2025 In LIPIcs : Leibniz international proceedings in informatics 339.
Abstract

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 ≤ n1/2−ϵ, and an exp(Ω(n1/3−ϵ)) lower bound for a function in P.

Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Clique, Colouring, Cutting planes, Lifting, Monotone circuit, Sunflower
host publication
40th Computational Complexity Conference, CCC 2025 : CCC 2025, August 5–8, 2025, Toronto, Canada - CCC 2025, August 5–8, 2025, Toronto, Canada
series title
LIPIcs : Leibniz international proceedings in informatics
editor
Srinivasan, Srikanth
volume
339
pages
19 pages
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
40th Computational Complexity Conference, CCC 2025
conference location
Toronto, Canada
conference dates
2025-08-05 - 2025-08-08
external identifiers
  • scopus:105012182286
ISSN
1868-8969
ISBN
9783959773799
DOI
10.4230/LIPIcs.CCC.2025.36
language
English
LU publication?
yes
id
d8ba1851-ed5b-4077-b539-c1a7993f9091
date added to LUP
2025-08-12 10:33:17
date last changed
2025-10-14 12:36:49
@inproceedings{d8ba1851-ed5b-4077-b539-c1a7993f9091,
  abstract     = {{<p>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<sup>Ω(k)</sup> lower bound for the clique function up to k ≤ n<sup>1/2−ϵ</sup>, and an exp(Ω(n<sup>1/3−ϵ</sup>)) lower bound for a function in P.</p>}},
  author       = {{de Rezende, Susanna F. and Vinyals, Marc}},
  booktitle    = {{40th Computational Complexity Conference, CCC 2025 : CCC 2025, August 5–8, 2025, Toronto, Canada}},
  editor       = {{Srinivasan, Srikanth}},
  isbn         = {{9783959773799}},
  issn         = {{1868-8969}},
  keywords     = {{Clique; Colouring; Cutting planes; Lifting; Monotone circuit; Sunflower}},
  language     = {{eng}},
  month        = {{07}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{LIPIcs : Leibniz international proceedings in informatics}},
  title        = {{Lifting with colourful sunflowers}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.CCC.2025.36}},
  doi          = {{10.4230/LIPIcs.CCC.2025.36}},
  volume       = {{339}},
  year         = {{2025}},
}