ﻻ يوجد ملخص باللغة العربية
For every $epsilon>0$, we give an $exp(tilde{O}(sqrt{n}/epsilon^2))$-time algorithm for the $1$ vs $1-epsilon$ emph{Best Separable State (BSS)} problem of distinguishing, given an $n^2times n^2$ matrix $mathcal{M}$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $rho$ that $mathcal{M}$ accepts with probability $1$, and the case that every separable state is accepted with probability at most $1-epsilon$. Equivalently, our algorithm takes the description of a subspace $mathcal{W} subseteq mathbb{F}^{n^2}$ (where $mathbb{F}$ can be either the real or complex field) and distinguishes between the case that $mathcal{W}$ contains a rank one matrix, and the case that every rank one matrix is at least $epsilon$ far (in $ell_2$ distance) from $mathcal{W}$. To the best of our knowledge, this is the first improvement over the brute-force $exp(n)$-time algorithm for this problem. Our algorithm is based on the emph{sum-of-squares} hierarchy and its analysis is inspired by Lovetts proof (STOC 14, JACM 16) that the communication complexity of every rank-$n$ Boolean matrix is bounded by $tilde{O}(sqrt{n})$.
We study the computational complexity of approximating the 2->q norm of linear operators (defined as ||A||_{2->q} = sup_v ||Av||_q/||v||_2), as well as connections between this question and issues arising in quantum information theory and the study o
We study the log-rank conjecture from the perspective of point-hyperplane incidence geometry. We formulate the following conjecture: Given a point set in $mathbb{R}^d$ that is covered by constant-sized sets of parallel hyperplanes, there exists an af
In the noisy tensor completion problem we observe $m$ entries (whose location is chosen uniformly at random) from an unknown $n_1 times n_2 times n_3$ tensor $T$. We assume that $T$ is entry-wise close to being rank $r$. Our goal is to fill in its mi
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$
The goal of this article is to prove the Sum of Squares Conjecture for real polynomials $r(z,bar{z})$ on $mathbb{C}^3$ with diagonal coefficient matrix. This conjecture describes the possible values for the rank of $r(z,bar{z}) |z|^2$ under the hypot