Date & Time:
February 14, 2023 3:30 pm – 4:30 pm
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


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

UChicago CS News

Fred Chong Receives Quantrell Award for Excellence in Teaching

May 16, 2024
UChicago CS News

Non-Unital Noise Adds a New Wrinkle to the Quantum Supremacy Debate

Apr 05, 2024
UChicago CS News

Argonne scientists use AI to identify new materials for carbon capture

Feb 19, 2024
In the News

New research unites quantum engineering and artificial intelligence

Jan 29, 2024
UChicago CS News

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

Jan 09, 2024
UChicago CS News

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

Jul 25, 2023
UChicago CS News

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

Mar 27, 2023
Students posing at competition
UChicago CS News

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

Mar 17, 2023
UChicago CS News

Assistant Professor Robert Rand Receives Air Force Young Investigator Grant

Dec 19, 2022
Professor Fred Chong advising students
UChicago CS News

Prof. Fred Chong Reappointed to National Quantum Initiative Advisory Committee

Dec 13, 2022
UChicago CS News

Professor Fred Chong Named IEEE Fellow

Dec 09, 2022
UChicago CS News

Associate Professor Diana Franklin Named ACM Distinguished Member

Dec 07, 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