Derandomization and absolute reconstruction for sums of powers of linear forms
From MaRDI portal
Publication:820536
linear algebraarithmetic circuitstensor decompositionpolynomial identity testingcircuit reconstruction
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3935120 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- scientific article; zbMATH DE number 3409446 (Why is no real title available?)
- A Grothendieck ring of higher degree forms
- A Link between the Canonical Decomposition in Multilinear Algebra and Simultaneous Matrix Diagonalization
- Affine projections of polynomials (extended abstract)
- 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
- Algorithms in real algebraic geometry
- Characterization of entire functions via quadrature
- Complexity of ring morphism problems
- Computation of the Canonical Decomposition by Means of a Simultaneous Generalized Schur Decomposition
- Computing symmetric rank for symmetric tensors
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- Constructive non-commutative rank computation is in deterministic polynomial time
- Diagonal Circuit Identity Testing and Lower Bounds
- Efficient algorithms for some special cases of the polynomial equivalence problem
- Equivalence of $\mathbb{F}$ -Algebras and Cubic Forms
- Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
- Factoring multivariate polynomials via partial differential equations
- Four lectures on polynomial absolute factorization
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Interpolation of depth-3 arithmetic circuits with two multiplication gates
- Lifting and recombination techniques for absolute factorization
- Non-commutative Edmonds' problem and matrix semi-invariants
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- On cubic hypersurfaces with vanishing Hessian
- Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective
- Pencil-based algorithms for tensor rank decomposition are not stable
- Polynomial equivalence problems for sum of affine powers
- Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
- Random arithmetic formulas can be reconstructed efficiently
- Reconstruction of full rank algebraic branching programs
- Reconstruction of non-degenerate homogeneous depth three circuits
- Reducing the number of variables of a polynomial
- Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming
- Symmetric tensor decomposition
- Topology and factorization of polynomials
- Vanishing Hessian, wild forms and their border VSP
Cited in
(6)- A superfast randomized algorithm to decompose binary forms
- scientific article; zbMATH DE number 4061432 (Why is no real title available?)
- Polynomial equivalence problems for sum of affine powers
- On the Koiran-Skomra's question about Hessians
- Diagonalizable higher degree forms and symmetric tensors
- Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond
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)
