Monotone Rank and Separations in Computational Complexity
Yang D. Li · arXiv (Cornell University) · 2011
In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity. – We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to a longstanding open problem posed by Nisan [Nis91] in algebraic complexity. More specifically, we exhibit a homogeneous algebraic function f of degree d (d even) on n variables with the monotone algebraic branching program (ABP) complexity Ω(n) and the non-monotone ABP complexity O(d). – We propose a relaxed version of the famous Bell’s theorem [Bel64] [CHSH69]. Bell’s theorem basically states that local hidden variable theory cannot predict the correlations produced by quantum mechanics, and therefore is an impossibility result. Bell’s theorem heavily relies on the diversity of the measurements. We prove that even if we fix the measurement, infinite amount of local hidden variables will still be needed, though now the prediction of “quantum mechanics” becomes physically feasible. Quantitatively, at least n bits of local hidden variables are needed to simulate the correlations of size 2n generated from a 2-qubit Bell state. The bound is asymptotically tight. – We generalize the log-rank conjecture [LS88] in communication complexity to the multiparty case, and prove that for super-polynomial parties, there is a super-polynomial separation between the deterministic communication complexity and the logarithm of the rank of the communication tensor. This means that the log-rank conjecture does not hold in “high” dimensions.