SODA Conference 2023 Conference Paper
- Yeongwoo Hwang
- Joe Neeman
- Ojas Parekh
- Kevin Thompson 0007
- John Wright 0004
The Gaussian noise stability of a function f: ℝ n → {-1, 1} is the expected value of f ( x ) · f ( y ) over ρ-correlated Gaussian random variables x and y. Borell's inequality states that for —1 ≤ ρ ≤ 0, this is minimized by the mean-zero halfspace f ( x ) = sign( x 1 ). In this work, we conjecture that a natural generalization of this result holds for functions f: ℝ n → S k -1 which output k -dimensional unit vectors. Our main conjecture, which we call the vector-valued Borell's inequality, asserts that the expectation E x ~ρ y 〈 f(x), f ( y )〉 is minimized by the function f (x) = x≤ k /|| x ≤ k ||, where x ≤ k = ( x 1, …, x k ). We give several pieces of evidence in favor of this conjecture, including a proof that it does indeed hold in the special case of n = k. As an application of this conjecture, we show that it implies several hardness of approximation results for a special case of the local Hamiltonian problem related to the anti-ferromagnetic Heisenberg model known as Quantum Max-Cut. This can be viewed as a natural quantum analogue of the classical Max-Cut problem and has been proposed as a useful testbed for developing algorithms. We show the following, assuming the vector-valued Borell's inequality: 1. There exists an integrality gap of 0. 498 for the basic SDP, matching the rounding algorithm of Gharibian and Parekh [GP19]. Combined with the work of Anshu, Gosset, and Morenz [AGM20], this shows that the basic SDP does not achieve the optimal approximation ratio. 2. It is Unique Games-hard (UG-hard) to compute a (0. 956 + ε)-approximation to the value of the best product state, matching an approximation algorithm due to Briët, Oliveira, and Vallentin [BdOFV10]. 3. It is UG-hard to compute a (0. 956 + ε)-approximation to the value of the best (possibly entangled) state. Our results also apply to the problem of Rank- k MAX-CUT considered by Briet, Oliveira, and Vallentin [BdOFV10] and show that it is UG-hard to outperform their approximation algorithm for any fixed k, again assuming our conjecture.