The goal of the matrix completion problem is to retrieve an unknown real matrix from a small subset of its entries. This problem comes up in many application areas, and has received a great deal of attention in the context of the Netflix challenge. This setup usually represents our partial knowledge of some information domain. Unknown entries may be due to the unavailability of some relevant experimental data. One approach to this problem starts by selecting a complexity measure of matrices, such as rank or trace norm. The corresponding algorithm outputs a matrix of lowest possible complexity that agrees with the partially specified matrix. The performance of the above algorithm under the assumption that the revealed entries are sampled randomly has received considerable attention. We ask what can be said if the observed entries are chosen deterministically. We prove bounds for the guarantees of such deterministic algorithms, that resemble results for the randomized algorithms. The heart of our proof is a new structural property of matrices with low trace norm, which can be seen as a variant of Poincare inequality. Joint work with E. Heiman and G. Schechtman