[Colloquium] Theory Seminars at Computer Science

[Donna Brooms via Colloquium]

*REMINDER*

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/20161129/ad664b4a/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/20161129/ad664b4a/attachment-0001.docx>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161129/ad664b4a/attachment-0003.html>