[Theory] UC Theory Seminar: a reminder

[Alexander Razborov]

Aravindan Vijayaraghaven
Northwestern University
 
 

 
 
Tuesday, February 14, 2023 at 3:30pm
Kent Chemical Laboratory, Room 102
 
 
Title: Computing linear sections of varieties: quantum entanglement, tensordecompositions 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.

 



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230213/d8639c2b/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 24204 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230213/d8639c2b/attachment-0001.jpg>