Fetching the paper…
Reading the bibliography…
Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly.
Methodus incrementorum directa et inversa [direct and reverse methods of incrementation] (in latin)
Brook Taylor · 1969
Earlier work this paper cites.
On Hensel factorization, I
Hans Zassenhaus · 1969
Earlier work this paper cites.
Vermeidung von divisionen
Volker Strassen · 1973
Earlier work this paper cites.
Commutative algebra. II. Reprint of the 1960 edition
Oscar Zariski and Pierre Samuel · 1975
Earlier work this paper cites.
New NP-hard and NP-complete polynomial and integer divisibility problems
David Alan Plaisted · 1977
Earlier work this paper cites.
Sparse complex polynomials and polynomial reducibility
David Alan Plaisted · 1977
Earlier work this paper cites.
Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
Claus-Peter Schnorr · 1977
Earlier work this paper cites.
Evaluation of polynomials with super-preconditioning
Richard J Lipton and Larry J Stockmeyer · 1978
Earlier work this paper cites.
Completeness classes in algebra
Leslie G. Valiant · 1979
Earlier work this paper cites.
Fast probabilistic algorithms for verification of polynomial identities
J. T. Schwartz · 1980
Earlier work this paper cites.
Reducibility by algebraic projections in: Logic and algorithmic
L Valiant · 1982
Earlier work this paper cites.
Fast parallel computation of polynomials using few processors
Leslie G. Valiant, Sven Skyum, Stuart Berkowitz, and Charles Rackoff · 1983
Earlier work this paper cites.
Computing with polynomials given by straight-line programs I: greatest common divisors
Erich Kaltofen · 1985
Earlier work this paper cites.
Factoring sparse multivariate polynomials
Joachim von zur Gathen and Erich Kaltofen · 1985
Earlier work this paper cites.
On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
Philip E Gill, Walter Murray, Michael A Saunders, John A Tomlin, and Margaret H Wright · 1986
Earlier work this paper cites.
Uniform closure properties of p-computable functions
Erich Kaltofen · 1986
Earlier work this paper cites.
Single-factor hensel lifting and its application to the straight-line complexity of certain polynomials
Erich Kaltofen · 1987
Earlier work this paper cites.
Gröbner bases and primary decomposition of polynomial ideals
Patrizia Gianni, Barry Trager, and Gail Zacharias · 1988
Earlier work this paper cites.
On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines
Lenore Blum, Mike Shub, and Steve Smale · 1989
Earlier work this paper cites.
Factorization of polynomials given by straight-line programs
Erich Kaltofen · 1989
Earlier work this paper cites.
Polynomial factorization 1982-1986
Erich Kaltofen · 1990
Earlier work this paper cites.
The number field sieve
Arjen K Lenstra, Hendrik W Lenstra, Mark S Manasse, and John M Pollard · 1990
Earlier work this paper cites.
Computing algebraic formulas using a constant number of registers
Michael Ben-Or and Richard Cleve · 1992
Earlier work this paper cites.
Polynomial factorization 1987–1991
Erich Kaltofen · 1992
Cited alongside, same era.
What is Mathematics?: an elementary approach to ideas and methods
Richard Courant, Herbert Robbins, and Ian Stewart · 1996
Cited alongside, same era.
Finite Fields
Rudolph Lidl and Harald Niederreiter · 1997
Cited alongside, same era.
A combinatorial algorithm for the determinant
Meena Mahajan and V Vinay · 1997
Cited alongside, same era.
Decoding of reed solomon codes beyond the error-correction bound
Madhu Sudan · 1997
Cited alongside, same era.
Improved decoding of reed-solomon and algebraic-geometric codes
Venkatesan Guruswami and Madhu Sudan · 1998
Cited alongside, same era.
Trading grh for algebra: algorithms for factoring polynomials and related structures
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, and Nitin Saxena · 2012
Later among the works it cites.
The implicit function theorem: history, theory, and applications
Steven G Krantz and Harold R Parks · 2012
Later among the works it cites.
The GCT program toward the P vs. NP problem
Ketan D. Mulmuley · 2012
Later among the works it cites.
Geometric complexity theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether’s normalization lemma
Ketan D. Mulmuley · 2012
Later among the works it cites.
Algebraic complexity theory
Peter Bürgisser, Michael Clausen, and Amin Shokrollahi · 2013
Later among the works it cites.
Completeness and reduction in algebraic complexity theory
Peter Bürgisser · 2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
James M Ortega and Werner C Rheinboldt · 2000
Cited alongside, same era.
The complexity of factors of multivariate polynomials
Peter Bürgisser · 2001
Cited alongside, same era.
The complexity of factors of multivariate polynomials
Peter Bürgisser · 2001
Cited alongside, same era.
Factoring polynomials over local fields
Sebastian Pauli · 2001
Cited alongside, same era.
Quadratic newton iteration for systems with multiplicity
Grégoire Lecerf · 2002
Cited alongside, same era.
Derandomizing polynomial identity tests means proving circuit lower bounds
Valentine Kabanets and Russell Impagliazzo · 2003
Cited alongside, same era.
Later among the works it cites.
Modern computer algebra
Joachim von zur Gathen and Jürgen Gerhard · 2013
Later among the works it cites.
Homomorphism polynomials complete for VP
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh · 2014
Later among the works it cites.
Algebraic complexity classes
Meena Mahajan · 2014
Later among the works it cites.
Complexity theory column 88: Challenges in polynomial factorization
Michael A Forbes and Amir Shpilka · 2015
Later among the works it cites.
Unifying known lower bounds via geometric complexity theory
Joshua A Grochow · 2015
Later among the works it cites.
Equivalence of polynomial identity testing and polynomial factorization
Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka · 2015
Later among the works it cites.
Proof complexity lower bounds from algebraic circuit complexity
Michael A Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson · 2016
Later among the works it cites.
Boundaries of VP and VNP
Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao · 2016
Later among the works it cites.
Arithmetic circuits with locally low algebraic rank
Mrinal Kumar and Shubhangi Saraf · 2016
Later among the works it cites.
Factors of low individual degree polynomials
Rafael Oliveira · 2016
Later among the works it cites.
Algebraic independence over positive characteristic: New criterion and applications to locally low algebraic rank circuits
Anurag Pandey, Nitin Saxena, and Amit Sinhababu · 2016
Later among the works it cites.
A survey of lower bounds in arithmetic circuit complexity
Ramprasad Saptharishi · 2016
Later among the works it cites.
Reconstruction of real depth-3 circuits with top fan-in 2
Gaurav Sinha · 2016
Later among the works it cites.
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good
Manindra Agrawal, Michael Forbes, Sumanta Ghosh, and Nitin Saxena · 2017
Closest in time.
On algebraic branching programs of small width
Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam · 2017
Closest in time.
Geometric complexity theory V: Efficient algorithms for Noether normalization
Ketan Mulmuley · 2017
Closest in time.