文章基本信息

标题：A Quadratic Lower Bound for Algebraic Branching Programs
本地全文：下载
作者：Prerona Chatterjee ; Mrinal Kumar ; Adrian She 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：169
页码：2:1-2:21
DOI：10.4230/LIPIcs.CCC.2020.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We show that any Algebraic Branching Program (ABP) computing the polynomial â^'_{i=1}^n xâ¿_i has at least Î©(nÂ²) vertices. This improves upon the lower bound of Î©(nlog n), which follows from the classical result of Baur and Strassen [Volker Strassen, 1973; Walter Baur and Volker Strassen, 1983], and extends the results of Kumar [Mrinal Kumar, 2019], which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial. Our proof relies on a notion of depth reduction which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial â^'_{i=1}^n xâ¿_i can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial â^'_{i=1}^n xâ¿_i + Îµ(ð±), for a structured "error polynomial" Îµ(ð±). To complete the proof, we then observe that the lower bound in [Mrinal Kumar, 2019] is robust enough and continues to hold for all polynomials â^'_{i=1}^n xâ¿_i + Îµ(ð±), where Îµ(ð±) has the appropriate structure.
关键词：Algebraic Branching Programs; Lower Bound