Date & Time:
February 14, 2023 3:30 pm – 4:30 pm
Location:
Kent 102, 1020 E 58th St, Chicago, IL, 60637
02/14/2023 03:30 PM 02/14/2023 04:30 PM America/Chicago Aravindan Vijayaraghaven (Northwestern) – Computing Linear Sections of Varieties: Quantum Entanglement, Tensor Decompositions and Beyond Kent 102, 1020 E 58th St, Chicago, IL, 60637

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.

Host: Alexander Razborov

Speakers

Aravindan Vijayaraghaven

Associate Professor of Computer Science and Industrial Engineering & Management Sciences, Northwestern University

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.

Related News & Events

No Name

Argonne scientists use AI to identify new materials for carbon capture

Feb 19, 2024
No Name

New research unites quantum engineering and artificial intelligence

Jan 29, 2024
No Name

Group From UChicago CS To Present Four Papers at Most Prestigious International Quantum Conference

Jan 09, 2024
No Name

UChicago Scientists Make New Discovery Proving Entanglement Is Responsible for Computational Hardness In Quantum Systems

Jul 25, 2023
No Name

Virtual Bakery Game Serves Up Both Cupcakes and Quantum Concepts For K-12 Students

Mar 27, 2023
Students posing at competition
No Name

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
No Name

Assistant Professor Robert Rand Receives Air Force Young Investigator Grant

Dec 19, 2022
Professor Fred Chong advising students
No Name

Prof. Fred Chong Reappointed to National Quantum Initiative Advisory Committee

Dec 13, 2022
No Name

Professor Fred Chong Named IEEE Fellow

Dec 09, 2022
No Name

Associate Professor Diana Franklin Named ACM Distinguished Member

Dec 07, 2022
Haifeng Xu
No Name

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
No Name

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube