Tensor Reconstruction Beyond Constant Rank

Explore tensor reconstruction beyond constant rank in this 52-minute lecture from the Workshop on Tensors: Quantum Information, Complexity and Combinatorics. Delve into recent advancements in reconstructing restricted classes of algebraic circuits with bounded top fan-in, which yield an efficient algorithm for computing tensor rank for tensors of small but super-constant rank. Learn how this work improves upon and extends the Bhargava, Saraf, and Volkovich algorithm for the constant rank case. Examine the connections between tensor rank computation and algebraic circuit reconstruction, and understand the challenges and solutions in designing efficient algorithms for special cases of these NP-hard problems. Discover the BSV algorithm for low and high degree cases, syntactic rank of ΣΤΙΣ circuits, and methods for finding B explicitly and obtaining black box access to clusters. Conclude with a discussion of open problems in the field.