Seminars

View all Seminars  |  Download ICal for this event

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

Series: Ph.D. Colloquium

Speaker: Nikhil Gupta, Ph.D (Engg.) student, Dept. of CSA,

Date/Time: Jul 25 10:30:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor: Prof. Chandan Saha

Abstract:
Two n-variate polynomials f and g in F[x1,...,xn] are said to be equivalent over the field F if there exists an invertible matrix A over F such that f = g(Ax), where x = (x1...xn). The problem of testing whether f is equivalent to a polynomial g coming from a polynomial family G (or computed by a circuit C in a circuit class D) is called the equivalence test (in short, ET) for G (respectively, D). In this thesis, we study equivalence tests for the determinant polynomial family and the class of regular read-once arithmetic formulas (ROFs). We also study some structural and algorithmic properties related to the symmetries of the Nisan-Wigderson design polynomial (in short, NW) and solve an interesting special case of ET for NW.


In the first work, we study ET for the determinant (in short, DET) over finite fields and the field of rational numbers denoted Q. A randomized polynomial time DET over the field of complex numbers was given by Kayal in [Kay12]. But DET over finite fields and over Q were not known. We give the first randomized polynomial-time DET over finite fields and also give the first DET over Q. The DET over Q takes oracle access to an integer factoring algorithm (IntFact) and if the input polynomial f is equivalent to the n x n determinant over Q, then it outputs a certificate matrix A over Q. This algorithm is randomized and is efficient for bounded values of n. Assuming the generalized Riemann hypothesis, we also show that the problem of integer factoring reduces to DET for quadratic forms (i.e., n = 2 case). If the DET algorithm does not take oracle access to IntFact, then it outputs a certificate matrix over an extension field L of Q, where [L:Q]<=n. This variant of DET is also randomized and is efficient for any value of n. The DET algorithms over finite fields and Q are obtained by decomposing the Lie algebra of f and then invoking known algorithms for the full matrix algebra isomorphism (FMAI) problem over finite fields and Q. FMAI is a well-studied problem in computer algebra. We also give a reduction from FMAI to DET, which is efficient when n is bounded. This is joint work with Ankit Garg, Neeraj Kayal, and Chandan Saha.


In the second work, we study ET for read-once arithmetic formulas (ROFs). An ROF is an arithmetic formula where every leaf node is labeled by either a distinct variable or a constant from the underlying field. ROFs are well-studied in the literature. In this work, we give the first randomized polynomial-time ET with oracle access to quadratic form equivalence for certain restricted ROFs, which we call regular ROFs. ET for regular ROFs generalizes the well-known quadratic form equivalence problem over the field of complex numbers and ETs for the classes of sum-product polynomials and ROANFs. ETs for these two classes have been recently studied by Medini & Shpilka (2021). Our ET algorithm uses some crucial properties related to the non-zeroness, the factors, and essential variables of the Hessian determinant of a regular ROF. We study these properties for the Hessian determinant of an arbitrary ROF C by analyzing the structures and coefficients of some nice monomials in the Hessian determinant of C. This is joint work with Chandan Saha and Bhargav Thankey.


In the last work, we study some structural and algorithmic properties related to the symmetries of NW and give a special case of ET for NW. In NW, each pair of monomials has very few variables in common. This property of NW has been exploited to give strong lower bounds for different classes of arithmetic circuits. Like NW, other polynomials like the permanent, the determinant, etc., have also been extensively used in lower bound results. But unlike these polynomials, not much is known about NW. In this work, we study some important properties of NW related to its symmetries. A matrix A is said to be a symmetry of NW if NW(Ax) = NW. We show that NW is characterized by its symmetries over the field of complex numbers but not over the fields of real numbers and rational numbers. Using the symmetries of NW, we show that NW is characterized by circuit identities over any field. This result implies a randomized polynomial time circuit testing algorithm for NW - which tests whether some circuit C computes NW- and the flip theorem for NW. We also solve an interesting special case of ET for NW, which we call the block-diagonal permutation scaling ET for NW. This ET uses the symmetries of NW crucially. This is joint work with Chandan Saha.