Equivalence Test for Read-Once Arithmetic Formulas by Bhargav Thankey

Date : 10 Feb 2023
Speaker : Bhargav Thankey (Indian Institute of Science, Bangalore)

Description:
Abstract: We study the polynomial equivalence problem for orbits of read-once arithmetic formulas (ROFs). Read-once formulas have received considerable attention in both algebraic and Boolean complexity and have served as a testbed for developing effective tools and techniques for analyzing circuits. Two n-variate polynomials f, g in F[x_1, ..., x_n] are equivalent, denoted as f ~ g, if there is an A in GL(n, F) such that f = g(A(x_1, ..., x_n)^T). The orbit of f is the set of all polynomials equivalent to f. We investigate the complexity of the following two natural problems on ROFs:

1. Equivalence test for ROFs: Given black-box access to f, check if it is in the orbit of an ROF. If yes, output an ROF C and an A in GL(n, F) such that f = C(A(x_1, ..., x_n)^T).
2. Polynomial equivalence for orbits of ROFs: Given black-box access to f and g in the orbits of two unknown ROFs, check if f ~ g. If yes, output an A in GL(n, F) such that f = g(A(x_1, ..., x_n)^T).

These problems are significant generalisations of two well-studied problems in algebraic complexity, namely reconstruction of ROFs and quadratic form equivalence. In this work, we give the first randomized polynomial-time algorithms (with oracle access to quadratic form equivalence) to solve the two problems. The equivalence test works for general ROFs; it also implies an efficient learning algorithm for random arithmetic formulas of unbounded depth and fan-in (in the high number of variables setting). The algorithm for the second problem, which invokes the equivalence test, works for mildly restricted ROFs, namely additive-constant-free ROFs.  
      
The equivalence test is based on a novel interplay between the factors and the essential variables of the Hessian determinant of an ROF, the essential variables of the ROF, and certain special structures in the ROF that we call "skewed paths". To our knowledge, the Hessian of a general ROF (or even a depth-4 ROF) has not been analysed before. Analysing the Hessian and combining the knowledge gained from it with the skewed paths to recursively discover formulas in the orbits of sub-ROFs of lower depth (without incurring an exponential blow-up due to unbounded depth) constitute the main technical contributions of this work.