## Generalized matrix completion and algebraic natural proofs

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language | English |
---|---|

Title of host publication | STOC 2018 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |

Number of pages | 13 |

Place of Publication | New York |

Publisher | Association for Computing Machinery |

Publication date | 20 Jun 2018 |

Pages | 17-29 |

DOIs | |

Publication status | Published - 20 Jun 2018 |

Externally published | Yes |

Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018 |

### Conference

Conference | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|

Land | United States |

By | Los Angeles |

Periode | 25/06/2018 → 29/06/2018 |

Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) |

Series | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN | 0737-8017 |

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

### Research areas

ID: 232711612