Seminars
View all Seminars | Download ICal for this eventEquivalence 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: