[Colloquium] CS Theory Seminar - Aravindan Vijayaraghaven, February 14, 2023

[Jose J Fragoso]

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/20230214/d15a302a/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/20230214/d15a302a/attachment-0001.jpg>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230214/d15a302a/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00002.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230214/d15a302a/attachment-0003.txt>