Raz's recent result \cite{Raz2010} has rekindled people's interest in the study of \emph{tensor rank}, the generalization of matrix rank to high dimensions, by showing its connections to arithmetic formulas. In this paper, we follow Raz's work and show that \emph{monotone rank}, the monotone variant of tensor rank and matrix rank, has applications in algebraic complexity, quantum computing and communication complexity. A common point of tensor rank and monotone rank is that they are both NP-hard to compute \cite{Has1990, Vav2009}, and are also hard to bound. This paper differs from Raz's paper in that it leverages existing results to show unconditional bounds while Raz's result relies on some assumptions.
More concretely, we show the following things.
\begin{itemize}
\item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus provide a strong solution to Nisan's question \cite{Nis1991} in algebraic complexity. More specifically, we exhibit that there exists a homogeneous algebraic function $f$ of degree $d$ ($d$ even) on $n$ variables with the monotone algebraic branching program (ABP) complexity $\Omega(d^2\log n)$ and the non-monotone ABP complexity $O(d^2)$.
\item In Bell's theorem\cite{Bel1964, CHSH1969}, a basic assumption is that players have free will, and under such an assumption, local hidden variable theory still cannot predict the correlations produced by quantum mechanics. Using tools from monotone rank, we show that even if we disallow the players to have free will, local hidden variable theory still cannot predict the correlations produced by quantum mechanics.
\item We generalize the log-rank conjecture \cite{LS1988} 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.
\end{itemize}
I fixed the bug, as pointed out by Pavel Hrubes.
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.
\begin{itemize}
\item 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 \cite{Nis1991} 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 $\Omega(n^{d/2})$ and the non-monotone ABP complexity $O(d^2)$.
\item We propose a relaxed version of the famous Bell's theorem\cite{Bel1964}\cite{CHSH1969}. 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.
\item We generalize the log-rank conjecture \cite{LS1988} 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.
\end{itemize}
This is no fault of the author - the mistake is in the paper LC10.
