On symmetries of and equivalence tests for two polynomial families and a circuit class

Abstract

Two polynomials f, g ∈ F[x1, . . . , xn] over a field F are said to be equivalent if there exists an n×n invertible matrix A over F such that g = f(Ax), where x = (x1 · · · xn)T . The equivalence test (in short, ET) for a polynomial family {fm}m∈N (similarly, a circuit class C ) is the following algorithmic problem: Given input black-box access to g ∈ F[x1, . . . , xn], determine whether there exists an f ∈ {fm}m∈N (respectively, a circuit C ∈ C ) such that g = f(Ax) (respectively, g = C(Ax)) for some n × n invertible matrix A over F. If the answer is yes, it also outputs an f ∈ {fm}m∈N (respectively, a circuit C ∈ C ) and an n × n invertible certificate matrix A over F such that g = f(Ax) (respectively, g = C(Ax)). In this thesis, we study equivalence tests for two polynomial families, namely the families of Nisan-Wigderson design polynomials (in short, NW) and determinant, and a circuit class, namely the class of regular read-once arithmetic formulas. In the process of designing ET for NW, we prove some fundamental structural and algorithmic results related to the symmetries of NW, namely characterization by symmetries, characterization by circuit identities, a circuit testing algorithm and a flip theorem. An invertible matrix A is called a symmetry of NW if NW = NW(Ax). In the first work, we study some useful properties of the symmetries of NW. NW is an important polynomial in algebraic complexity theory (ACT) as it has been used to prove lower bounds for various classes of arithmetic circuits. Similar to NW, other polynomials like the determinant, the permanent, the IMM, etc. have also been used in many lower bound proofs in ACT. Unlike these polynomials, which are well-studied, not much is known about NW. The family of NW is in VNP but it is not known whether it is in VP and or is VNP-complete. In this work, we fill in some gaps in our understanding of NW by answering certain interesting questions related to the symmetries of NW. These questions are quite relevant from the context of geometric complexity theory and have been studied for the permanent. We show that NW is characterized by its symmetries over C but not over R and Q. Using the symmetries of NW, we show that NW is characterized by circuit identities over any field. By exploiting the second property, we give a randomized polynomial time circuit testing algorithm and a flip theorem for NW. A circuit testing algorithm checks whether a given circuit computes NW and hence is a natural special case of ET for NW. A circuit testing algorithm is also required for the ET for NW. We give a randomized polynomial time reduction from general ET for NW to the block-permuted ET for NW. Further, we also give a randomized polynomial time algorithm for a special case of block-permuted ET for NW, which we call block-diagonal permutation scaling ET for NW. These structural and algorithmic results crucially use some special symmetries of NW as well as the structure of the group of symmetries of NW, denoted GNW. The structure of GNW was studied in the author’s master’s thesis [Gup17] and is not included in this thesis. In the second work, we study ET for the family of determinant (in short, DET) over finite fields and over Q. A randomized polynomial time DET over C was given in [Kay12]. A randomized polynomial time DET over a finite field Fq was given in [KNS19], which outputs a certificate matrix over a degree n extension field of Fq, provided the input polynomial is equivalent to the n × n determinant, denoted Detn. In this work, we give a randomized polynomial time DET over Fq, which outputs a certificate matrix over the base field. We also give the first randomized DET over Q, which takes oracle access to an integer factoring algorithm (IntFact), and outputs a certificate matrix over Q. This DET runs in polynomial time in the Turing machine model if n is bounded. If we remove oracle access to IntFact from DET over Q, then we get a polynomial time randomized DET for every n, but it outputs a certificate matrix over an extension field L of Q, where [L : Q] ≤ n. The heart of these algorithms is a randomized polynomial time reduction from DET to the full matrix algebra isomorphism (FMAI) problem. This reduction exploits the rich structure of the Lie algebra of the determinant and works over almost every field. FMAI is a well-studied problem in computer algebra and FMAI algorithms are known over finite fields and Q. We prove that assuming the Generalized Riemann Hypothesis, there exists a randomized polynomial time reduction from integer factoring to DET for quadratic forms over Q (i.e., n = 2 case). This shows that it is unlikely to get rid of the IntFact oracle from DET over Q. We also give a reduction from FMAI to DET over almost every field, which is efficient if n is bounded. This shows that FMAI and DET are randomized polynomial time reducible to each other whenever n is bounded. In the third work, we give the first randomized polynomial time equivalence test with oracle access to quadratic form equivalence (QFE) for the class of regular read-once arithmetic formulas (in short, regular ROFs). An arithmetic formula C over a field F is said to be read-once if every leaf node of C is labelled by either a distinct variable or a constant from F. ROFs are well-studied in the literature. An ROF C is called regular if every variable in C is a child of a × gate. Thus, the class of regular ROFs is a natural subclass of ROFs. An ET for regular ROFs significantly generalizes QFE over C and ET algorithms for two previously studied sub-classes of regular ROFs, namely the classes of sum-product polynomials and ROANFs. Equivalence tests for these two classes were given recently in [MS21]. Our ET algorithm is based on some useful properties of the Hessian determinant of a regular ROF like its non-zeroness, knowledge of its factors and its essential variables. The arbitrary nature of the underlying tree of a regular ROF makes the analysis of the above mentioned properties of its Hessian determinant technically challenging. We overcome this challenge by studying the structures and coefficients of some nice monomials in the Hessian determinant of a regular ROF.