Seminars

View all Seminars  |  Download ICal for this event

On the Complexity of Testing Equivalence to Design Polynomials, Sparse Polynomials, and the Hamiltonian Cycle Polynomial

Series: Ph.D. Colloquium

Speaker: Agrim Dewan, Ph.D (Engg.) student, Dept. of CSA, IISc.,

Date/Time: Oct 23 16:30:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Faculty Advisor: Prof. Chandan Saha

Abstract:
Two n-variate polynomials f, g in F[x], where F is a field, are said to be equivalent if there exists an n x n invertible matrix A over F and a translation vector b in F^n such that f(x) = g(Ax+b). Interpreted geometrically, equivalent polynomials are the same function up to an invertible change of coordinates. The Equivalence Testing problem for a polynomial family P, or ET for P, is as follows: Given black-box access to a polynomial f in F[x], decide if there exists a g in P such that f is equivalent to g. If such a g exists, then output an invertible matrix A and a vector b such that f = g(Ax + b). One can similarly define ET for a circuit class. ET has been studied for various important polynomial families, such as the Permanent and Determinant, and, more recently, for circuit classes such as Read-Once Formulas. In this thesis, we study the complexity of ET for design polynomials, for sparse polynomials, and for the Hamiltonian Cycle polynomial.

In our first work, we study ET for design polynomials. An n-variate degree-d polynomial g is called a (n,d,t) design polynomial if the degree of the gcd of every pair of monomials of g is at most t-1. An important example of design polynomials is the Nisan-Wigderson polynomial (NW). Introduced in (Kayal, Saha, Saptharishi; STOC 2014), NW has been used to prove lower bounds against constant-depth circuits. NW is in VNP, the algebraic analogue of NP, but is not known to be VNP-complete. In contrast, the Permanent polynomial family is known to be VNP-complete (Valiant; STOC 1979). An efficient ET algorithm is also known for the Permanent (Kayal; STOC 2012). However, a general ET algorithm was unknown for NW. In (Gupta, Saha; MFCS 2019), the authors gave an efficient ET algorithm for NW in a special case over the reals and certain finite fields, while ET for NW was unknown to be decidable over the rationals. A natural question is whether an ET algorithm exists for more general design polynomials. In a joint work with Omkar Baraskar and Chandan Saha, we present a randomised, polynomial in (nd)^t time algorithm that finds A and b, if they exist, such that f(Ax+b) is a (n,d,t) design polynomial provided t is at most d/3. The algorithm is obtained by using the Vector Space Decomposition framework developed in (Gupta, Kayal, Saha; FOCS 2020). This also yields an ET algorithm for NW over the rationals. As an application of the ET algorithm, we show a polynomial-time equivalence, under many-one reductions, between the Graph Isomorphism problem and the Polynomial Equivalence problem for design polynomials. We also show that a cryptographic scheme proposed by (Patarin; Eurocrypt 1996) can be broken in quasi-polynomial time if a random sparse polynomial is used in the key generation phase. Lastly, we give an efficient learning algorithm for n-variate random affine projections of multilinear degree-d design polynomials, provided n is at least d^4. If one obtains an analogous result under the weaker assumption