We give fast algorithms for low-rank tensor decomposition.
Over $\mathbb R$ and $\mathbb C$ we give a deterministic algorithm that takes as input an order-$d$, width-$n$, rank-$k$ tensor, gets measurement access to the tensor, runs in time
$k^{O(k^2)}\cdot \mathrm{poly}(n,d)$, and finds a minimal decomposition as a sum of rank-one ... more >>>

The problem of decomposing an algebraic variety into more structured components (such as equidimensional, irreducible, or connected components) is a fundamental problem in computer algebra and algebraic geometry. In this work, we study the computational complexity of computing equidimensional components of algebraic varieties, represented via Chow forms.

We improve the ... more >>>

We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with two-sided error. Namely, we show that any $q$-query RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+\Omega(1/q)}$, closely matching the ... more >>>