Abstract References

Some Recent Advancements in Monotone Circuit Complexity

Susanna F. de Rezende ORCID Lund University, Sweden
Abstract

In 1985, Razborov [16] proved the first superpolynomial size lower bound for monotone Boolean circuits for the perfect matching the clique functions, and, independently, Andreev [2] obtained exponential size lower bounds. These breakthroughs were soon followed by further advancements in monotone complexity, including better lower bounds for clique [1, 19], superlogarithmic depth lower bounds for connectivity by Karchmer and Wigderson [12], and the separations mon-NC≠mon-P and that mon-NCi≠mon-NCi+1 by Raz and McKenzie [15]. Karchmer and Wigderson [12] proved their result by establishing a relation between communication complexity and (monotone) circuit depth, and Raz and McKenzie [15] introduced a new technique, now called lifting theorems, for obtaining communication lower bounds from query complexity lower bounds,

In this talk, we will survey recent advancements in monotone complexity driven by query-to-communication lifting theorems. A decade ago, Göös, Pitassi, and Watson [10] brought to light the generality of the result of Raz and McKenzie [15] and reignited this line of work. A notable extension is the lifting theorem [8] for a model of DAG-like communication [17, 18] that corresponds to circuit size. These powerful theorems, in their different flavours, have been instrumental in addressing many open questions in monotone circuit complexity, including: optimal 2Ω⁢(n) lower bounds on the size of monotone Boolean formulas computing an explicit function in NP [14]; a complete picture of the relation between the mon-AC and mon-NC hierarchies [6]; a near optimal separation between monotone circuit and monotone formula size [5]; exponential separation between NC2 and mon-P [8, 11]; and better lower bounds for clique [7, 13], improving on [3]. Very recently, lifting theorems were also used to prove supercritical trade-offs for monotone circuits showing that there are functions computable by small circuits for which any small circuit must have superlinear or even superpolynomial depth [4, 9]. We will explore these results and their implications, and conclude by discussing some open problems.

Keywords and phrases:
monotone circuit complexity, query complexity, lifting theorems
Category:
Invited Talk
Copyright and License:
[Uncaptioned image] © Susanna F. de Rezende; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Circuit complexity ; Theory of computation → Communication complexity ; Theory of computation → Proof complexity
Funding:
ELLIIT, Knut and Alice Wallenberg grants KAW 2021.0307 and 2023.0116, and the Swedish Research Council grant 2021-05104.
DOI:
10.4230/LIPIcs.STACS.2025.4
Event:
42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
Editors:
Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng
Series and Publisher:
LIPIcs Logo Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

References

  • [1] Noga Alon and Ravi B. Boppana. The monotone circuit complexity of Boolean functions. Combinatorica, 7(1):1–22, March 1987. doi:10.1007/bf02579196.
  • [2] Alexander E. Andreev. On a method for obtaining lower bounds for the complexity of individual monotone functions. Soviet Mathematics Doklady, 31(3):530–534, 1985. English translation of a paper in Doklady Akademii Nauk SSSR.
  • [3] Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman. Monotone circuit lower bounds from robust sunflowers. In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN ’20), volume 12118 of Lecture Notes in Computer Science, pages 311–322. Springer, January 2021. doi:10.1007/978-3-030-61792-9_25.
  • [4] Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, and Shuo Pang. Truly supercritical trade-offs for resolution, cutting planes, monotone circuits, and weisfeiler-leman. Technical Report 2411.14267, arXiv.org, November 2024. doi:10.48550/arXiv.2411.14267.
  • [5] Susanna F. de Rezende, Or Meir, Jakob Nordstrom, Toniann Pitassi, Robert Robere, and Marc Vinyals. Lifting with simple gadgets and applications to circuit and proof complexity. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS ’20), November 2020. doi:10.1109/focs46700.2020.00011.
  • [6] Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. How limited interaction hinders real communication (and what it means for proof and circuit complexity). In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS ’16), October 2016. doi:10.1109/focs.2016.40.
  • [7] Susanna F. de Rezende and Marc Vinyals. Lifting with colourful sunflowers. Manuscript, 2025.
  • [8] Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory of Computing, 16(13):1–30, 2020. Preliminary version in STOC ’18. doi:10.4086/toc.2020.v016a013.
  • [9] Mika Göös, Gilbert Maystre, Kilian Risse, and Dmitry Sokolov. Supercritical tradeoffs for monotone circuits. Technical Report 2411.14268, arXiv.org, November 2024. doi:10.48550/arXiv.2411.14268.
  • [10] Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM Journal on Computing, 47(6):2435–2450, January 2018. Preliminary version in FOCS ’15. doi:10.1137/16m1059369.
  • [11] Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in monotone complexity and TFNP. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS ’19), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:19, January 2019. doi:10.4230/LIPIcs.ITCS.2019.38.
  • [12] Mauricio Karchmer and Avi Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255–265, 1990. Preliminary version in STOC ’88. doi:10.1137/0403021.
  • [13] Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with Sunflowers. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS ’22), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 104:1–104:24, January 2022. doi:10.4230/LIPICS.ITCS.2022.104.
  • [14] Toniann Pitassi and Robert Robere. Strongly exponential lower bounds for monotone computation. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC ’17), pages 1246–1255, June 2017. doi:10.1145/3055399.3055478.
  • [15] Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Combinatorica, 19(3):403–435, March 1999. Preliminary version in FOCS ’97. doi:10.1007/s004930050062.
  • [16] Alexander A. Razborov. Lower bounds for the monotone complexity of some Boolean functions. Soviet Mathematics Doklady, 31(2):354–357, 1985. English translation of a paper in Doklady Akademii Nauk SSSR.
  • [17] Alexander A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya: Mathematics, pages 205–227, February 1995. doi:10.1070/im1995v059n01abeh000009.
  • [18] Dmitry Sokolov. Dag-like communication and its applications. In Proceedings of the 12th International Computer Science Symposium in Russia (CSR ’17), volume 10304 of Lecture Notes in Computer Science, pages 294–307. Springer, June 2017. doi:10.1007/978-3-319-58747-9_26.
  • [19] Ingo Wegener. The complexity of Boolean functions. Wiley-Teubner, 1987. URL: http://ls2-www.cs.uni-dortmund.de/monographs/bluebook/.