Department of Mathematics Calendar

Back to Listing

The Department of Mathematics is a bustling place full of new ideas. We host several events that occur throughout the year, including seminars, colloquium, conferences, and social events. Our seminars and colloquium are open to the public: all students, faculty, or alumni who are interested are welcome to join us for exciting talks on the leading edge of mathematics research!

For information about adding events to this calendar, please see this user guide

Decision and Control Laboratory and the Illinois Institute for Data Science and Dynamical Systems || Professor Leonid Gurvits|| A Poly-time DETERMINISTIC Algorithm for Simply Exponential Approximation of the Permanent of PSD Matrices and Other Cool Quantum Things

Event Type
Decision and Control Laboratory and the Illinois Institute for Data Science and Dynamical Systems
141 Computer Science Laboratory
Sep 26, 2022   1:00 pm  
Professor Leonid Gurvits | The City College of New York
Stephanie McCullough

Leonid Gurvits is a Professor of Computer Science at the City College of New York. He is known for fundamental contributions to the theory of nonholonomic motion planning, computational complexity, and classical and quantum computation. His proof of van der Waerden’s permanent conjecture has been included as a chapter in the sixth edition of Martin Aigner and Günter Ziegler’s “Proofs from THE BOOK.”


I will first explain the importance of the permanent of PSD matrices in Quantum Linear
Optics, and put it into more general concept of so called quantum permanent of bipartite
density matrices.

In this talk I will show how to get a cn approximation algorithm for the permanent of
PSD matrices, where c is a universal constant (prior to this result not even random-
ized poly-time algorithm with (even) worst case simply exponential relative
error was known); and en approximation algorithm for the quantum permanent of sep-
arable, aka non-entangled, bipartite density matrices.

Our algorithm is based on a semide nite program with a convex nonlinear objective.
Our proof of its correctness is essentially a New Van Der Waerden Like Lower Bound:
What is the smallest value of the permanent of projectors on images of n n
correlation matrices?

If time permits, I will talk about how our result can \save" the recently refuted
permanent-on-top conjecture as well as its application to approximating the largest eigen-
value of certain n! n! PSD matrices.
Based on the joint work with Nima Anari, Shayan Oveis Gharan, Amin Saberi.

link for robots only