Derandomization and absolute reconstruction for sums of powers of linear forms
DOI10.1016/j.tcs.2021.07.005zbMath1483.13044arXiv1912.02021OpenAlexW3198950050MaRDI QIDQ820536
Publication date: 27 September 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.02021
linear algebratensor decompositionarithmetic circuitspolynomial identity testingcircuit reconstruction
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) Multilinear algebra, tensor calculus (15A69) Computational methods for problems pertaining to field theory (12-08) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On cubic hypersurfaces with vanishing Hessian
- Random arithmetic formulas can be reconstructed efficiently
- Symmetric tensor 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
- A Grothendieck ring of higher degree forms
- Vanishing Hessian, wild forms and their border VSP
- Reconstruction algorithms for sums of affine powers
- Lifting and recombination techniques for absolute factorization
- Non-commutative Edmonds' problem and matrix semi-invariants
- Complexity of ring morphism problems
- 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
- Diagonal Circuit Identity Testing and Lower Bounds
- Topology and factorization of polynomials
- Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
- Characterization of entire functions via quadrature
- 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.
- Computation of the Canonical Decomposition by Means of a Simultaneous Generalized Schur Decomposition
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Factoring multivariate polynomials via partial differential equations
- 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
- 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
- Affine projections of polynomials
- Equivalence of $\mathbb{F}$ -Algebras and Cubic Forms
- Quasi-polynomial hitting-set for set-depth-Δ formulas
- Algorithms in real algebraic geometry
This page was built for publication: Derandomization and absolute reconstruction for sums of powers of linear forms