Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing (STOC), pages {653--664}, 2017) and independently by Grochow, Kumar, Saks and Saraf~(CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich's famous barrier result (J. Comput. Syst. Sci., 55(1): 24--35, 1997) for Boolean circuit complexity to algebraic complexity theory. Razborov and Rudich's barrier result relies on a widely believed assumption, namely, the existence of pseudo-random generators. Unfortunately, there is no known analogous theory of pseudo-randomness in the algebraic setting. Therefore, Forbes et al.~use a concept called succinct hitting sets instead. This assumption is related to polynomial identity testing, but it is currently not clear how plausible this assumption is. Forbes et al.~are only able to construct succinct hitting sets against rather weak models of arithmetic circuits.

Generalized matrix completion is the following problem: Given a matrix with affine linear forms as entries, find an assignment to the variables in the linear forms such that the rank of the resulting matrix is minimal. We call this rank the completion rank. Computing the completion rank is an NP -hard problem. As our first main result, we prove that it is also NP -hard to determine whether a given matrix can be approximated by matrices of completion rank b . The minimum quantity b for which this is possible is called border completion rank (similar to the border rank of tensors). Naturally, algebraic natural proofs can only prove lower bounds for such border complexity measures. Furthermore, these border complexity measures play an important role in the geometric complexity program.

Using our hardness result above, we can prove the following barrier: We construct a small family of matrices with affine linear forms as entries and a bound b , such that at least one of these matrices does not have an algebraic natural proof of polynomial size against all matrices of border completion rank b , unless coNP BPP . This is an algebraic barrier result that is based on a well-established and widely believed conjecture. The complexity class BPP is known to be a subset of the more well known complexity class MA in the literature. Thus BPP can be replaced by MA in the statements of all our results. With similar techniques, we can also prove that tensor rank is hard to approximate. Furthermore, we prove a similar result for the variety of matrices with permanent zero. There are no algebraic polynomial size natural proofs for the variety of matrices with permanent zero, unless P # P BPP . On the other hand, we are able to prove that the geometric complexity theory approach initiated by Mulmuley and Sohoni ({SIAM} J. Comput. 31(2): 496--526, 2001) yields proofs of polynomial size for this variety, therefore overcoming the natural proofs barrier in this case.