On Orbits and Border of Constant Read Circuits and Lower Bounds for Constant Depth Circuits

Abstract

Two of the most common ways in which arithmetic circuits can be restricted is by requiring that they be constant read or constant depth. Constant depth circuits have received a lot of attention in the arithmetic circuit literature as proving strong enough lower bounds for constant depth arithmetic circuits imply lower bounds for general arithmetic circuits. The orbits of constant read models are extremely interesting because the orbit closures (i.e. the border of the orbit) of some constant read models capture arithmetic formulas and algebraic branching programs. We study some problems about the orbits and borders of certain constant read models as well as the lower bound problem for constant depth arithmetic circuits.

The orbit of f in F[x_1, ..., x_n] is defined as orb(f) = {f(Ax + b): A in GL(n, F), b in F^n}, where x = (x_1 ... x_n)^T. The orbit of a circuit class C is defined as the union of the orbits of all polynomials computable by circuits in C. In our first work, we study the (black-box) PIT problem for the orbits of low individual degree commutative ROABPs, multilinear constant width ROABPs, constant depth constant occur formulas, and occur once formulas. We give quasi-polynomial time PIT algorithms for all four models. As corollaries, we get quasi-polynomial PIT algorithms for polynomial families like IMM_{3, d}, power and elementary symmetric polynomials, as well as sum-product polynomials.

In our second work, we study the equivalence test problem for read-once arithmetic formulas (ROFs) as well as the polynomial equivalence problem for the orbits of ROFs. f, g are said to be equivalent if g is in orb(f). The equivalence test problem for ROFs is as follows: given black-box access to f, check if it is in the orbit of an ROF. If yes, output an ROF R A in GL(n, F), b in F^n such that f = R(Ax + b). The polynomial equivalence problem for the orbits of ROFs is the following: given black-box access to f, g in the orbits of two unknown ROFs, determine if f and g are equivalent. If yes, then output A in GL(n, F), b in F^n such that g = f(Ax + b). We give randomised polynomial time algorithms for both these problems. Our algorithm for the second problem works for orbits of mildly restricted ROFs, namely for the orbits of additive constant free ROFs.

In our third work, we study the lower bounds problem for constant depth arithmetic circuits. In a breakthrough work, Limaye, Srinivasan, and Tavenas (FOCS 2021) resolved the long-standing open problem of proving super polynomial lower bounds for constant depth arithmetic circuits. We give a more direct proof of their result by avoiding a crucial “hardness escalation” step in their proof. As this step introduces an exponential blow-up in the circuit size, our proof opens up the possibility of proving exponential lower bounds for constant-depth homogeneous circuits.

Finally, in our fourth work, we study the border of sums of 2 ROFs. The border of a circuit class C consists of all polynomials that can be “approximated” by a sequence of polynomials computable by circuits in C. The border of ROFs is contained in ROFs. We show that the class of sum of k many n-variate ROFs is not closed under the border for 2 <= k <= n/5. Nevertheless, we prove that the border of sums of 2 additive constant free ROFs is contained in the sum of O(n) many ROFs. We also give a quasi-polynomial time PIT algorithm for the border of the sum of 2 homogeneous depth-5 ROFs.