Appears in collection : 2024 - PC2 - Random tensors and related topics

The "hay in a haystack" problem is to find an explicit object that behaves like a random one in terms of its complexity. A tensor version of this problem is to find an explicit tensor in some tensor space that has maximal border rank (i.e., maximal complexity), in other words the border rank of a random tensor. A stronger version is to find an explicit sequence, of say (m,m,m) tensors as m goes to infinity, with maximal border rank. The state of the art for this problem is embarrassing. Arora and Barak refer to lower bounds as "Complexity theory's Waterloo". I'll report on the little that is known and try to explain why the problem is so difficult.