Chatterjee, Prerona
Separating ABPs and Some Structured Formulas in the NonCommutative Setting
Abstract
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 noncommutative 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 noncommutative 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 superpolynomial lower bound against abecedarian formulas for f_{log n, n}(𝐱) would separate the powers of formulas and ABPs in the noncommutative setting.
BibTeX  Entry
@InProceedings{chatterjee:LIPIcs.CCC.2021.7,
author = {Chatterjee, Prerona},
title = {{Separating ABPs and Some Structured Formulas in the NonCommutative Setting}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {7:17:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771931},
ISSN = {18688969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14281},
URN = {urn:nbn:de:0030drops142812},
doi = {10.4230/LIPIcs.CCC.2021.7},
annote = {Keywords: NonCommutative Formulas, Lower Bound, Separating ABPs and Formulas}
}
08.07.2021
Keywords: 

NonCommutative Formulas, Lower Bound, Separating ABPs and Formulas 
Seminar: 

36th Computational Complexity Conference (CCC 2021)

Issue date: 

2021 
Date of publication: 

08.07.2021 