Discovering the roots: uniform closure results for algebraic classes under factoring

DOI10.1145/3188745.3188760zbMath1428.68398arXiv1710.03214OpenAlexW2964068501MaRDI QIDQ5230370

Amit Sinhababu, Nitin Saxena, Pranjal Dutta

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

polynomial factorizationroots of polynomialshardnesscircuit factorization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Computational methods for problems pertaining to field theory (12-08)

Related Items (6)

A note on VNP-completeness and border complexity ⋮ Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits ⋮ Schur polynomials do not have small formulas if the determinant does not ⋮ Unnamed Item ⋮ Factorization of polynomials given by arithmetic branching programs ⋮ Factorization of polynomials given by arithmetic branching programs

This page was built for publication: Discovering the roots: uniform closure results for algebraic classes under factoring