Limitations of Sums of Bounded-Read Formulas
share
Proving super polynomial size lower bounds for various classes of arithmetic circuits computing explicit polynomials is a very important and challenging task in algebraic complexity theory. We study representation of polynomials as sums of weaker models such as read once formulas (ROFs) and read once oblivious algebraic branching programs (ROABPs). We prove: (1) An exponential separation between sum of ROFs and read-k formulas for some constant k. (2) A sub-exponential separation between sum of ROABPs and syntactic multilinear ABPs. Our results are based on analysis of the partial derivative matrix under different distributions. These results highlight richness of bounded read restrictions in arithmetic formulas and ABPs. Finally, we consider a generalization of multilinear ROABPs known as strict-interval ABPs defined in [Ramya-Rao, MFCS2019]. We show that strict-interval ABPs are equivalent to ROABPs upto a polynomial size blow up. In contrast, we show that interval formulas are different from ROFs and also admit depth reduction which is not known in the case of strict-interval ABPs.
READ FULL TEXT