2026-07-21T19:38:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14281 2024-03-06T10:53:51Z ddc:004 open_access

Separating ABPs and Some Structured Formulas in the Non-Commutative Setting Chatterjee, Prerona Non-Commutative Formulas Lower Bound Separating ABPs and Formulas The motivating question for this work is a long standing open problem, posed by Nisan [Noam Nisan, 1991], regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question remains open, we make some progress towards its resolution. To that effect, we generalise the notion of ordered polynomials in the non-commutative setting (defined by Hrubeš, Wigderson and Yehudayoff [Hrubeš et al., 2011]) to define abecedarian polynomials and models that naturally compute them. Our main contribution is a possible new approach towards resolving the VF_{nc} vs VBP_{nc} question, via lower bounds against abecedarian formulas. In particular, we show the following. There is an explicit n²-variate degree d abecedarian polynomial f_{n,d}(𝐱) such that - f_{n, d}(𝐱) can be computed by an abecedarian ABP of size O(nd); - any abecedarian formula computing f_{n, log n}(𝐱) must have size at least n^{Ω(log log n)}. We also show that a super-polynomial lower bound against abecedarian formulas for f_{log n, n}(𝐱) would separate the powers of formulas and ABPs in the non-commutative setting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prerona Chatterjee 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.7 urn:nbn:de:0030-drops-142812 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode