[Colloquium] CS Theory Seminar - Aravindan Vijayaraghaven, February 14, 2023
Jose J Fragoso
jfragoso at uchicago.edu
Mon Feb 13 08:45:41 CST 2023
UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS
Aravindan Vijayaraghaven
Northwestern University
[cid:image001.jpg at 01D936F1.E9B87B20]
Tuesday, February 14, 2023 at 3:30pm
Kent Chemical Laboratory, Room 102
Title: Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
Abstract: Abstract: We study the problem of finding elements in the intersection of an arbitrary conic variety (over reals or complex numbers) with a given linear subspace. This problem captures a rich family of algorithmic problems under different choices of the variety. The special case of the variety consisting of rank-1 matrices already has strong connections to central problems in different areas like quantum information theory and tensor decompositions.
>
> Despite the worst-case NP-hardness of this problem, we give efficient algorithms that solve this problem for "typical" subspaces i.e., those chosen generically of a certain dimension, potentially with some generic elements of the variety contained in it, under some mild non-degeneracy assumptions on the variety. These also imply new algorithmic results for low-rank decomposition problems that go beyond tensor decompositions, and problems in quantum entanglement.
>
> This is based on joint work with Nathaniel Johnston and Benjamin Lovitz.
Bio: I’m an Associate Professor of Computer Science and Industrial Engineering & Management Sciences at Northwestern University in Evanston, IL. I received my PhD in Computer Science from Princeton University.
Host: Alexander Razborov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230213/3e557bff/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 24204 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230213/3e557bff/attachment-0001.jpg>
More information about the Colloquium
mailing list