{"ID":2871907,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.10450","arxiv_id":"2509.10450","title":"A linear-time algorithm for Chow decompositions","abstract":"We propose a linear-time algorithm to compute low-rank Chow decompositions. Our algorithm can decompose concise symmetric 3-tensors in n variables of Chow rank n/3. The algorithm is pencil based, hence it relies on generalized eigenvalue computations. We also develop sub-quadratic time algorithms for higher order Chow decompositions, and Chow decompositions of 3-tensors into products of linear forms which do not lie on the generic orbit. In particular, we obtain a sub-quadratic-time algorithm for decomposing a symmetric 3-tensor into a linear combination of W-tensors.","short_abstract":"We propose a linear-time algorithm to compute low-rank Chow decompositions. Our algorithm can decompose concise symmetric 3-tensors in n variables of Chow rank n/3. The algorithm is pencil based, hence it relies on generalized eigenvalue computations. We also develop sub-quadratic time algorithms for higher order Chow...","url_abs":"https://arxiv.org/abs/2509.10450","url_pdf":"https://arxiv.org/pdf/2509.10450v1","authors":"[\"Alexander Taveira Blomenhofer\",\"Benjamin Lovitz\"]","published":"2025-09-12T17:56:44Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.AG\",\"quant-ph\"]","methods":"[]","has_code":false}