Quantum computers are in general believed to be more powerful than classical computers, but it is not clear if they are powerful enough to solve problems that a classical computer can’t even verify.
In this talk, I will discuss the following connections between private optimization and statistical physics in the context of the low-rank matrix approximation problem:
The Gaussian correlation inequality (GCI), proven by Royen in 2014, states that any two centrally symmetric convex sets (say K and L) in the Gaussian space are positively correlated.
