2026-07-22T10:53:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18283 2024-03-06T11:01:30Z ddc:004 open_access

New Lower Bounds Against Homogeneous Non-Commutative Circuits Chatterjee, Prerona Hrubeš, Pavel Algebraic circuit complexity Non-Commutative Circuits Homogeneous Computation Lower bounds against algebraic circuits We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree d which requires homogeneous non-commutative circuit of size Ω(d/log d). For an n-variate polynomial with n > 1, the result can be improved to Ω(nd), if d ≤ n, or Ω(nd (log n)/(log d)), if d ≥ n. Under the same assumptions, we also give a quadratic lower bound for the ordered version of the central symmetric polynomial. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prerona Chatterjee and Pavel Hrubeš 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.13 urn:nbn:de:0030-drops-182835 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.13 eng https://creativecommons.org/licenses/by/4.0/legalcode