2026-08-21T18:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27440 2026-08-21T14:42:40Z ddc:004 open_access

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials Komarath, Balagopal Narayanan, Rohit Monotone complexity bounded depth formula complexity graph homomorphism algebraic complexity We introduce baggy elimination trees, a novel graph decomposition that generalises the classical elimination trees underlying treedepth, and use them to give a complete characterisation of the monotone bounded-depth formula complexity of graph homomorphism and coloured isomorphism polynomials. Specifically, we prove that the Δ-product depth monotone formula complexity of these polynomials is Θ(n^λ_Δ(H)), where λ_Δ(H) is the minimum cost of a baggy elimination tree for H at BET-depth Δ. This result closes the last open case in the programme initiated by Komarath, Pandey and Rahul [Balagopal Komarath et al., 2023] and continued by Bhargav, Chen, Curticapean and Dwivedi [C. S. Bhargav et al., 2025]: tight size characterisations of monotone circuit complexity (via treewidth / bounded-depth treewidth), monotone ABP complexity (via pathwidth / bounded-depth pathwidth), and monotone formula complexity (via treedepth) were already known; our theorem supplies the missing bounded-depth formula characterisation via the new notion of bounded-depth baggy-elimination-tree cost λ_Δ, completing the picture for all three models in algebraic complexity and their fixed depth variants. As applications, for constant-degree polynomial families we derive an almost-optimal separation between monotone circuits and monotone formulas at every fixed product depth: there exists a family computable by O(N)-size monotone circuits of product depth Δ that requires Ω(N^{Δ/2})-size monotone formulas of the same depth (and this exponent is optimal up to a constant factor). We also prove a strict depth hierarchy: for every Δ ≥ 1 and every constant k ≥ 2, there is a constant-degree family with O(s(N))-size monotone formulas of product depth Δ that requires Ω(s(N)^k)-size monotone formulas of product depth Δ - 1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Balagopal Komarath and Rohit Narayanan 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.58 urn:nbn:de:0030-drops-274406 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.58 eng https://creativecommons.org/licenses/by/4.0/legalcode