Derandomization and absolute reconstruction for sums of powers of linear forms

DOI10.1016/J.TCS.2021.07.005zbMATH Open1483.13044arXiv1912.02021OpenAlexW3198950050MaRDI QIDQ820536FDOQ820536

Authors: Pascal Koiran, Mateusz Skomra 

Publication date: 27 September 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We study the decomposition of multivariate polynomials as sums of powers of linear forms. As one of our main results we give an algorithm for the following problem: given a homogeneous polynomial of degree 3, decide whether it can be written as a sum of cubes of linearly independent linear forms with complex coefficients. Compared to previous algorithms for the same problem, the two main novel features of this algorithm are: (i) It is an algebraic algorithm, i.e., it performs only arithmetic operations and equality tests on the coefficients of the input polynomial. In particular, it does not make any appeal to polynomial factorization. (ii) For an input polynomial with rational coefficients, the algorithm runs in polynomial time when implemented in the bit model of computation. The algorithm relies on methods from linear and multilinear algebra (symmetric tensor decomposition by simultaneous diagonalization). We also give a version of our algorithm for decomposition over the field of real numbers. In this case, the algorithm performs arithmetic operations and comparisons on the input coefficients. Finally we give several related derandomization results on black box polynomial identity testing, the minimization of the number of variables in a polynomial, the computation of Lie algebras and factorization into products of linear forms.

Full work available at URL: https://arxiv.org/abs/1912.02021

Recommendations

• Polynomial equivalence problems for sum of affine powers
• A nearly optimal algorithm to decompose binary forms
• scientific article; zbMATH DE number 1775429
• Decomposition Algorithms for Tensors and Polynomials
• Reconstruction algorithms for sums of affine powers

zbMATH Keywords

linear algebraarithmetic circuitstensor decompositionpolynomial identity testingcircuit reconstruction

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in real and complex fields: factorization (12D05) Polynomials, factorization in commutative rings (13P05) Networks and circuits as models of computation; circuit complexity (68Q06) Computational methods for problems pertaining to field theory (12-08)

Cites Work

• Title not available (Why is that?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Non-commutative Edmonds' problem and matrix semi-invariants
• Algorithms in real algebraic geometry
• Computation of the Canonical Decomposition by Means of a Simultaneous Generalized Schur Decomposition
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• A Link between the Canonical Decomposition in Multilinear Algebra and Simultaneous Matrix Diagonalization
• Symmetric tensor decomposition
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Title not available (Why is that?)
• Reducing the number of variables of a polynomial
• Affine projections of polynomials (extended abstract)
• Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
• Title not available (Why is that?)
• Factoring multivariate polynomials via partial differential equations
• Computing symmetric rank for symmetric tensors
• A Grothendieck ring of higher degree forms
• Characterization of entire functions via quadrature
• Lifting and recombination techniques for absolute factorization
• Complexity of ring morphism problems
• On cubic hypersurfaces with vanishing Hessian
• Interpolation of depth-3 arithmetic circuits with two multiplication gates
• Random arithmetic formulas can be reconstructed efficiently
• Title not available (Why is that?)
• Diagonal Circuit Identity Testing and Lower Bounds
• Vanishing Hessian, wild forms and their border VSP
• Four lectures on polynomial absolute factorization
• Topology and factorization of polynomials
• Reconstruction algorithms for sums of affine powers
• Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming
• Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
• Algorithmic Aspects of Machine Learning
• Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing
• Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time.
• Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective
• Polynomial Equivalence Problems for Sum of Affine Powers
• Reconstruction of Full Rank Algebraic Branching Programs
• Reconstruction of non-degenerate homogeneous depth three circuits
• Pencil-Based Algorithms for Tensor Rank Decomposition are not Stable
• Equivalence of $\mathbb{F}$ -Algebras and Cubic Forms

Cited In (5)

• Reconstruction algorithms for sums of affine powers
• Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond
• Title not available (Why is that?)
• On the Koiran-Skomra's question about Hessians
• Diagonalizable higher degree forms and symmetric tensors

This page was built for publication: Derandomization and absolute reconstruction for sums of powers of linear forms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820536)