Generalized matrix completion and algebraic natural proofs

DOI10.1145/3188745.3188832zbMath1427.68104OpenAlexW2809620386MaRDI QIDQ5230373

Gorav Jindal, Christian Ikenmeyer, Markus Bläser, Vladimir Lysikov

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3188745.3188832

zbMATH Keywords

matrix completiontensor rankgeometric complexity theoryalgebraic natural proofscompletion rank

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (6)

The tensor rank of semifields of order 16 and 81 ⋮ Tensor Rank is Hard to Approximate ⋮ Unnamed Item ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ Unnamed Item

This page was built for publication: Generalized matrix completion and algebraic natural proofs