[CSDM] [pvsnp-all] CCI meeting, Fri Mar 8: Grothendieck inequalities

[Moses S. Charikar]

Dear all,

We will have our monthly CCI meeting this Fri, March 8 in CS 402.
Assaf Naor and Oded Regev have agreed to entertain us with recent 
progress on Grothendieck inequalities and their applications; 
in some cases, newly established inequalities looking for applications. 

Schedule and abstracts are below.

Cheers,
Moses

10:!5-11:00 PI meeting
11:00-noon Algorithmic applications of the noncommutative Grothendieck
inequality-I
noon-1:00  lunch
1:00-2:00  Algorithmic applications of the noncommutative Grothendieck
inequality-II
2:00-2:30  break
2:30-4:00  Grothendieck inequalities in quantum games and a proof of the
operator space Grothendieck inequality


Title: Algorithmic applications of the noncommutative Grothendieck
inequality.
Speaker: Assaf Naor, Courant Institute, NYU

Abstract: In 1953 Grothendick proved an inequality of immense importance
to several areas of mathematics, as well as having interesting
applications to combinatorial optimization. In the same paper Grothendieck
also conjectured the validity of a "noncommutative" version of his
inequality, a conjecture that was solved affirmatively by Pisier in 1978,
yielding an important tool for the study of C^* algebras. This talk is
devoted to a description of algorithmic implications of the noncommutative
Grothendieck inequality. The talk will be self-contained and does not
assume any background other than basic linear algebra and probability. We
will start with a quick description of the classical Grothendieck
inequality, explain how it leads to its noncommutative counterpart, and
present a proof of the inequality that is an interesting rounding
algorithm for a certain semidefinite program. The efficiency of this
algorithm yields several algorithmic applications that we will describe,
including the first constant factor approximation algorithms for the
orthogonal Procrustes problem and robust versions of principle component
analysis (PCA).

Joint work with Oded Regev and Thomas Vidick.


Title: Grothendieck inequalities in quantum games and a proof of the
operator space Grothendieck inequality
Speaker: Oded Regev, Courant Institute, NYU

Abstract:
One of the most striking consequences of quantum mechanics (dating back
to Einstein et al.) is that two remote parties who share entanglement
can exhibit correlations that are impossible without entanglement. I
will describe the history of this problem and its connection (mainly due
to Tsirelson) to Grothendieck's inequality. I will then describe our
recent work on *quantum XOR games* and discuss their connection to the
non-commutative Grothendieck inequality and to the very recent
*operator-space Grothendieck inequality*.

We will then discuss our recent new proof of the operator-space
Grothendieck inequality, which is based on intuitions coming from
quantum information and computer science.

Based on two papers with Thomas Vidick.

_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all