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.

Intro
PROBLEMS REGARDING ALGEBRAIC CIRCUITS
RECONSTRUCTION OF ALGEBRAIC CIRCUITS
CONNECTIONS TO TENSOR RANK
RECONSTRUCTION OF ΣΤΙΣ CIRCUITS
MOTIVATION
BSV ALGORITHM: LOW DEGREE CASE
SYNTACTIC RANK OF ΣΤΙΣ CIRCUIT
BSV ALGORITHM: HIGH DEGREE CASE
FINDING B EXPLICITLY
OUR ALGORITHM FOR FINDING B
OBTAINING BLACK BOX ACCESS TO CLUSTERS
OPEN PROBLEMS