Seminars

View all Seminars  |  Download ICal for this event

Equivalence test for the trace iterated matrix multiplication polynomial

Series: M.Tech (Research) Colloquium

Speaker: Ms. Janaky Murthy M.Tech (Research) student Dept. of CSA IISc

Date/Time: Dec 17 11:00:00

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Faculty Advisor: Prof. Chandan Saha

Abstract:
An m-variate polynomial f is affine equivalent to an n-variate polynomial g if m ≥ n and there is a rank n matrix A ∈ Fn×m and b ∈ Fnsuch that f (x) = g(Ax + b). Given blackbox access to f and g (i.e membership query access) the affine equivalence test problem is to determine whether f is affine equivalent to g, and if yes then output a rank n matrix A ∈ Fn×m and b ∈ Fn such that f (x) = g(Ax + b). This problem is at least as hard as graph isomorphism and algebra isomorphism even when the coefficients of f and g are given explicitly (Agarwal and Saxena, STACS 2006), and has been studied in literature by fixing g to be some interesting family of polynomials. In this work, we fix g to be the trace of the product of d, w × w symbolic matrices X1,...,Xd. We call this polynomial Tr-IMMw,d. Kayal, Nair, Saha and Tavenas (CCC 2017) gave an efficient (i.e (mwd) O(1) time)randomized algorithm for the affine equivalence test of the iterated matrix multiplication polynomial IMMw,d, which is the (1,1)-th entry of the product of d w×w symbolic matrices. Although the definitions of Tr-IMMw,d and IMMw,d are closely related and their circuit complexities are very similar, it is not clear whether an efficient affine equivalence test algorithm for IMMw,d implies the same for Tr-IMMw,d. In this thesis, we take a step towards showing that equivalence test for Tr-IMMw,d and IMMw,d have different complexity. We show that equivalence test for Tr-IMMw,d reduces in randomized polynomial time to equivalence test for the determinant (DET), under mild conditions on the underlying field. If the converse is also true then equivalence tests for Tr-IMMw,d and DET are randomized polynomial time equivalent. It would then follow from the work of Gupta, Garg, Kayal and Saha (ICALP 2019) that equivalence test for Tr-IMMw,d over Q is at least as hard as Integer Factoring. This would then be in sharp contrast with the complexity of equivalence test for IMMw,d over Q which can be solved efficiently in randomized polynomial time (by Kayal, Nair, Saha and Tavenas (CCC 2017)). Recent Update: Soon after the thesis is written, we (together with Vineet Nair) have succeeded in showing the converse direction. So, the above conclusion is indeed true!

Speaker Bio:

Host Faculty: