BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20191217T120000Z
UID:c7a0352ec84b478e0eaeffbf6760f9a5-25
DTSTAMP:19700101T120011Z
DESCRIPTION:Equivalence test for the trace iterated matrix multiplication polynomial
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/25/equivalence-test-for-the-trace-iterated-matrix-multiplication-polynomial/
SUMMARY: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!
DTSTART:20191217T120000Z
END:VEVENT
END:VCALENDAR