[Colloquium] Theory Seminars at Computer Science
Donna Brooms via Colloquium
colloquium at mailman.cs.uchicago.edu
Tue Nov 22 14:47:31 CST 2016
Combinatorics and TCS seminar
Tuesday, November 29, 2016
Ry 251 @ 3pm
Youming Qiao
University of Technology, Sydney
Title: Isometry testing of Hermitian bilinear maps via *-algebras
Abstract:
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.
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.
Joint work with Gábor Ivanyos.
Host: Prof. Laszlo Babai
*Refreshments during the talk*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161122/1317a1be/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Jimmy.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 216618 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161122/1317a1be/attachment-0001.docx>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161122/1317a1be/attachment-0003.html>
More information about the Colloquium
mailing list