Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring

DOI10.1145/3510359OpenAlexW2762239886MaRDI QIDQ5889792

Nitin Saxena, Pranjal Dutta, Amit Sinhababu

Publication date: 27 April 2023

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3510359

zbMATH Keywords

randomizedformulaVBPVPVNPhardcircuit factoringABPquasipolyVF

Mathematics Subject Classification ID

Computer science (68-XX)

Uses Software

• Mulprec

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factors of low individual degree polynomials
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• A unified method for multivariate polynomial factorizations
• Factoring sparse multivariate polynomials
• Gröbner bases and primary decomposition of polynomial ideals
• Factoring polynomials with rational coefficients
• Algorithm of polynomial complexity for factoring polynomials over local fields
• Sparse complex polynomials and polynomial reducibility
• Evaluation of polynomials with super-preconditioning
• A probabilistic remark on algebraic program testing
• Decoding of Reed Solomon codes beyond the error-correction bound
• Straight-line programs in geometric elimination theory
• Completeness and reduction in algebraic complexity theory
• The complexity of factors of multivariate polynomials
• Quadratic Newton iteration for systems with multiplicity
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• Equivalence of polynomial identity testing and polynomial factorization
• Unifying known lower bounds via geometric complexity theory
• Complexity of ring morphism problems
• On Hensel factorization. I
• Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
• Bounded-degree factors of lacunary multivariate polynomials
• A Hensel lifting to replace factorization in list-decoding of algebraic-geometric and Reed-Solomon codes
• Algebraic Complexity Classes
• Geometric complexity theory V: Efficient algorithms for Noether normalization
• Modern Computer Algebra
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• Trading GRH for algebra: Algorithms for factoring polynomials and related structures
• Numerical Methods in Scientific Computing, Volume I
• A Course in Commutative Algebra
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• Factoring Polynomials over Algebraic Number Fields
• Hensel and Newton Methods in Valuation Rings
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• A New Algorithm for Factoring Polynomials Over Finite Fields
• Computing Algebraic Formulas Using a Constant Number of Registers
• All Algebraic Functions Can Be Computed Fast
• Fast Algorithms for Manipulating Formal Power Series
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Boundaries of VP and VNP
• Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits
• On Algebraic Branching Programs of Small Width
• The Computational Power of Depth Five Arithmetic Circuits
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
• Factoring multivariate polynomials via partial differential equations
• Factorization of polynomials given by arithmetic branching programs
• Fast Computation of the Roots of Polynomials Over the Ring of Power Series
• Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
• Bootstrapping variables in algebraic circuits
• Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits
• Expressing a fraction of two determinants as a determinant
• Proof Complexity Lower Bounds from Algebraic Circuit Complexity
• A modified Newton method for polynomials
• Factoring Polynomials Over Large Finite Fields
• Algèbre
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Factoring polynomials over local fields.

This page was built for publication: Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring