文章基本信息
- 标题：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
