[Colloquium] Theory Speaker Today
Donna Brooms
donna at cs.uchicago.edu
Tue May 24 07:36:34 CDT 2016
Combinatorics & Theory Seminar Today:
Today, Tuesday, May 24, 2016
Ry 251 @ 3pm
Youming Qiao (University of Technology, Sydney)
Title: Quantum matching problems
Abstract:
We describe two algorithmic problems, both of which can be viewed as quantum analogues of the perfect matching problem on bipartite graphs. Given several square matrices, we are asked to:
(1) decide if there is a full-rank matrix in their linear span
(2) decide if there is a shrunk subspace, that is a subspace U, s.t. the union of the images under these matrices is of smaller dimension than U.
The first problem is the well-known polynomial identity testing problem, for which a deterministic efficient solution implies a strong arithmetic circuit lower bound. The second problem has a rich history and has appeared in various forms in a remarkable number of mathematical and computational areas. For example, it is a key problem in the theory of non-commutative arithmetic circuits with divisions, as recently studied by Hrubes and Wigderson.
After introducing these problems, we will present a couple of ingredients in our recent deterministic efficient algorithm for the second problem. These include a polynomial degree upper bound on generating the ring of matrix semi-invariants, and a linear algebraic analogue of the augmenting path technique.
Based on joint works with Gabor Ivanyos and K. V. Subrahmanyam, arXiv:1508.00690 and arXiv:1512.03531. Another recent paper on this topic is arxiv:1511.03730.
Host: Prof. Babai
Refreshments will be served before the talk in Ry 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160524/ff38e5e5/attachment-0002.htm
-------------- next part --------------
A non-text attachment was scrubbed...
Name: The University of Chicago.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 193314 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160524/ff38e5e5/attachment-0001.bin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160524/ff38e5e5/attachment-0003.htm
More information about the Colloquium
mailing list