<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><font color="#ff2600" class=""><u class="">*REMINDER*</u></font></div><font color="#ff2600" class=""><u class=""><div class=""><font color="#ff2600" class=""><u class=""><br class=""></u></font></div>Combinatorics and TCS seminar</u></font><br class=""><br class="">Tuesday, November 29, 2016<br class="">Ry 251 @ 3pm<br class=""><br class=""><b class="">Youming Qiao</b><br class="">University of Technology, Sydney<br class=""><br class="">Title: Isometry testing of Hermitian bilinear maps via *-algebras<br class=""><br class="">Abstract:<br class="">Let F be a finite field of odd characteristic. Suppose we are given two tuples of n by n symmetric (resp. skew-symmetric) matrices vB=(B_1, ..., B_m) and vC=(C_1, ..., C_m) over F. vB and vC are isometric, if there exists an invertible matrix A such that for every i in [m], A^tB_iA=C_i. We present an efficient randomized algorithm to test whether vB and vC are isometric, in time polynomial in n, m, and log |F|. This algorithm is achieved by working with the underlying *-algebra (algebras with an anti-automorphism of order 2) of this problem.<br class=""><br class="">Our algorithm breaks an authentication protocol based on 1-sided isomorphism of quadratic forms, proposed by Patarin in 1990's. It also has certain consequence on isomorphism testing of p-groups of class 2 and exponent p, where p is odd.<br class=""><br class="">Joint work with Gábor Ivanyos.<br class=""><br class="">Host: Prof. Laszlo Babai<br class=""><br class="">*Refreshments during the talk*<br class=""><br class=""> </body></html>