Computer Science – Computational Complexity
Scientific paper
2011-02-15
Computer Science
Computational Complexity
A bug was fixed. Submitted to IEEE complexity 2012
Scientific paper
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. 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. 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)$. 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. 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.
No associations
LandOfFree
Applications of Monotone Rank to Complexity Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Applications of Monotone Rank to Complexity Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Applications of Monotone Rank to Complexity Theory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-377719