| dc.description.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. | en_US |
