We show that any language in nondeterministic time $\exp(\exp(\cdots\exp(n)))$, where the number of iterated exponentials is an arbitrary function $R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness $1$ and soundness $1 - \exp(-C\exp(\cdots\exp(n)))$, ... more >>>

The standard models of testing graph properties postulate that the vertex-set consists of $\{1,2,...,n\}$, where $n$ is a natural number that is given explicitly to the tester.
Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set ... more >>>

We consider relative error low rank approximation of tensors with respect to the Frobenius norm. Namely, given an order-$q$ tensor $A \in \mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$ tensor $B$ for which $\|A-B\|_F^2 \leq (1+\epsilon) {\rm OPT}$, where ${\rm OPT} = \inf_{\textrm{rank-}k~A'} \|A-A'\|_F^2$. Despite much success on obtaining relative error low ... more >>>