Generalized Matrix Completion and Algebraic Natural Proofs

Blaeser, Markus, Ikenmeyer, Christian, Jindal, Gorav and Lysikov, Vladimir (2018) Generalized Matrix Completion and Algebraic Natural Proofs. In: STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing.

Access the full-text of this item by clicking on the Open Access link.

Official URL: https://dl.acm.org/doi/10.1145/3188745.3188832

Abstract

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.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Algebraic natural proofs, matrix completion, tensor rank, completion rank, geometric complexity theory
Depositing User:	Symplectic Admin
Date Deposited:	20 Jan 2020 08:28
Last Modified:	19 Jan 2023 00:12
DOI:	10.1145/3188745.3188832
Open Access URL:	https://eccc.weizmann.ac.il/report/2018/064/downlo...
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3067059