2026-07-25T18:31:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19741 2024-03-11T06:37:04Z ddc:004 open_access

On the Power of Border Width-2 ABPs over Fields of Characteristic 2 Dutta, Pranjal Ikenmeyer, Christian Komarath, Balagopal Mittal, Harshil Nanoti, Saraswati Girish Thakkar, Dhara Algebraic branching programs border complexity characteristic 2 The celebrated result by Ben-Or and Cleve [SICOMP92] showed that algebraic formulas are polynomially equivalent to width-3 algebraic branching programs (ABP) for computing polynomials. i.e., VF = VBP₃. Further, there are simple polynomials, such as ∑_{i = 1}⁸ x_i y_i, that cannot be computed by width-2 ABPs [Allender and Wang, CC16]. Bringmann, Ikenmeyer and Zuiddam, [JACM18], on the other hand, studied these questions in the setting of approximate (i.e., border complexity) computation, and showed the universality of border width-2 ABPs, over fields of characteristic ≠ 2. In particular, they showed that polynomials that can be approximated by formulas can also be approximated (with only a polynomial blowup in size) by width-2 ABPs, i.e., VF ̅ = VBP₂ ̅. The power of border width-2 algebraic branching programs when the characteristic of the field is 2 was left open. In this paper, we show that width-2 ABPs can approximate every polynomial irrespective of the field characteristic. We show that any polynomial f with 𝓁 monomials and with at most t odd-power indeterminates per monomial can be approximated by 𝒪(𝓁⋅ (deg(f)+2^t))-size width-2 ABPs. Since 𝓁 and t are finite, this proves universality of border width-2 ABPs. For univariate polynomials, we improve this upper-bound from O(deg(f)²) to O(deg(f)). Moreover, we show that, if a polynomial f can be approximated by small formulas, then the polynomial f^d, for some small power d, can be approximated by small width-2 ABPs. Therefore, even over fields of characteristic two, border width-2 ABPs are a reasonably powerful computational model. Our construction works over any field. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pranjal Dutta and Christian Ikenmeyer and Balagopal Komarath and Harshil Mittal and Saraswati Girish Nanoti and Dhara Thakkar 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.31 urn:nbn:de:0030-drops-197419 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode