Generalized matrix completion and algebraic natural proofs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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.

Original languageEnglish
Title of host publicationSTOC 2018 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Number of pages13
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Publication date20 Jun 2018
Publication statusPublished - 20 Jun 2018
Externally publishedYes
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: 25 Jun 201829 Jun 2018


Conference50th Annual ACM Symposium on Theory of Computing, STOC 2018
LandUnited States
ByLos Angeles
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT)
SeriesProceedings of the Annual ACM Symposium on Theory of Computing

    Research areas

  • Algebraic natural proofs, Completion rank, Geometric complexity theory, Matrix completion, Tensor rank

ID: 232711612