期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question continues to remain 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 Hrubes, Wigderson and Yehudayoff (2011)) to define abecedarian polynomials and models that naturally compute them. Our main contribution is a possible new approach towards separating formulas and ABPs in the non-commutative setting, via lower bounds against abecedarian formulas. In particular, we show the following. There is an explicit n-variate degree d abecedarian polynomial fnd(x) such that 1. fnd(x) can be computed by an abecedarian ABP of size O(nd); 2. any abecedarian formula computing fnlogn(x) must have size that is super-polynomial in n. We also show that a super-polynomial lower bound against abecedarian formulas for flognn(x) would separate the powers of formulas and ABPs in the non-commutative setting.
关键词：algebraic circuit complexity;Formula vs ABP;Non Commutative Computation
