School of Mathematics

In quantum complexity theory, QMA and QCMA represent two different generalizations of NP. Both are defined as sets of languages whose Yes instances can be efficiently checked by a quantum verifier that is given a witness. With QMA the witness can be...

Tensors of Minimal Border Rank

Joseph Landsberg

A class of tensors, called "concise (m,m,m)-tensors  of minimal border rank", play an important role in proving upper bounds for the complexity of matrix multiplication. For that reason Problem 15.2 of "Algebraic Complexity Theory" by Bürgisser...