Abstract: We present a generalization of the collaborative filtering algorithm for the task of tensor estimation, i.e. estimating a low-rank 3-order n-by-n-by-n tensor from noisy observations of randomly chosen entries in the sparse regime. Not only does the algorithm have desirable computational properties, it also provably achieves sample complexity that (nearly) matches the conjectured lower bound on the sample complexity. Furthermore, our analysis results in high probability bounds on the infinity norm of the error, as opposed to the weaker MSE bounds achieved by previous approaches. Our proposed algorithm uses the matrix obtained from the “flattened” tensor to compute similarity with respect to a corresponding observation graph. The algorithm recovers the tensor with max entrywise error decaying to 0 with high probability as long as the entries are sampled uniformly at a density of Omega(n^{-3/2 + ε}) for any arbitrarily small ε > 0. This sample complexity threshold (nearly) matches a conjectured lower bound as well as the “connectivity threshold” of the corresponding observation graph used in our algorithm, providing a different angle to explain the conjectured lower bound.