Erich Kaltofen

According to our database1, Erich Kaltofen
  • authored at least 140 papers between 1981 and 2017.
  • has a "Dijkstra number"2 of four.

Awards

ACM Fellow

ACM Fellow 2009, "For contributions to symbolic and algebraic computation, algebraic algorithms and complexity theory.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2017
Computing Approximate Greatest Common Right Divisors of Differential Polynomials.
CoRR, 2017

Early Termination in Parametric Linear System Solving and Rational Function Vector Recovery with Error Correction.
Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, 2017

Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits.
Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, 2017

2016
Sparse multivariate function recovery with a small number of evaluations.
J. Symb. Comput., 2016

Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix.
CoRR, 2016

Numerical Sparsity Determination and Early Termination.
Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, 2016

Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix.
Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, 2016

2015
Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices.
CoRR, 2015

Jenks prize 2015 award citation.
ACM Comm. Computer Algebra, 2015

Error-Correcting Sparse Interpolation in the Chebyshev Basis.
Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, 2015

2014
Sparse Polynomial Interpolation Codes and their decoding beyond half the minimal distance.
CoRR, 2014

Essentially optimal interactive certificates in linear algebra.
CoRR, 2014

Numerical Linear System Solving with Parametric Entries by Error Correction.
ACM Comm. Computer Algebra, 2014

Cleaning-up data for sparse model synthesis: when symbolic-numeric computation meets error-correcting codes.
Proceedings of the Symbolic-Numeric Computation 2014, 2014

Numerical linear system solving with parametric entries by error correction.
Proceedings of the Symbolic-Numeric Computation 2014, 2014

Sparse multivariate function recovery with a high error rate in the evaluations.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2014

Sparse polynomial interpolation codes and their decoding beyond half the minimum distance.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2014

Essentially optimal interactive certificates in linear algebra.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2014

2013
On the matrix berlekamp-massey algorithm.
ACM Trans. Algorithms, 2013

NSF funding opportunities for symbolic computation.
ACM Comm. Computer Algebra, 2013

Jenks prize 2013 award citation.
ACM Comm. Computer Algebra, 2013

Sparse multivariate function recovery from values with noise and outlier errors.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2013

2012
Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients.
J. Symb. Comput., 2012

Special Issue on Symbolic and Algebraic Computation Foundations, Algorithmics and Applications: ISSAC 2009.
J. Symb. Comput., 2012

On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field.
J. Symb. Comput., 2012

Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2012

Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2012

Symbolic Computation and Complexity Theory Transcript of My Talk.
Proceedings of the Computer Mathematics, 2012

Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations.
Proceedings of the Computer Mathematics, 2012

2011
What is Hybrid Symbolic-Numeric Computation?
Proceedings of the 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2011

Symmetric Determinantal Representation of Weakly-Skew Circuits.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Fast estimates of Hankel matrix condition numbers and numeric sparse interpolation.
Proceedings of the SNC 2011, 2011

Quadratic-time certificates in linear algebra.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2011

Supersparse black box rational function interpolation.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2011

2010
Symmetric Determinantal Representation of Formulas and Weakly Skew Circuits
CoRR, 2010

Efficiently Certifying Non-Integer Powers.
Computational Complexity, 2010

Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2010

Fifteen years after DSC and WLSS2 what parallel computations I do today: invited lecture at PASCO 2010.
Proceedings of the 4th International Workshop on Parallel Symbolic Computation, 2010

2009
A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functions.
Proceedings of the Symbolic Numeric Computation, 2009

09471 Executive Summary - Computer-assisted proofs - tools, methods and applications.
Proceedings of the Computer-assisted proofs - tools, methods and applications, 15.11., 2009

09471 Abstracts Collection - Computer-assisted proofs - tools, methods and applications.
Proceedings of the Computer-assisted proofs - tools, methods and applications, 15.11., 2009

2008
Approximate factorization of multivariate polynomials using singular value decomposition.
J. Symb. Comput., 2008

Computing minimal generators of integer matrix sequences (abstract only).
ACM Comm. Computer Algebra, 2008

Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2008

Expressing a fraction of two determinants as a determinant.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2008

2007
Irreducible polynomials and barker sequences.
ACM Comm. Computer Algebra, 2007

On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms.
Proceedings of the Symbolic-Numeric Computation, 2007

On exact and approximate interpolation of sparse rational functions.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2007

Lower bounds for approximate factorizations via semidefinite programming: (extended abstract).
Proceedings of the Symbolic-Numeric Computation, 2007

2006
Hybrid symbolic-numeric computation.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2006

Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2006

Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2006

06271 Abstracts Collection -- Challenges in Symbolic Computation Software.
Proceedings of the Challenges in Symbolic Computation Software, 02.07. - 07.07.2006, 2006

06271 Executive Summary - Challenges in Symbolic Computation Software.
Proceedings of the Challenges in Symbolic Computation Software, 02.07. - 07.07.2006, 2006

2005
On the complexity of computing determinants.
Computational Complexity, 2005

Generic matrix multiplication and memory management in linBox.
Proceedings of the Symbolic and Algebraic Computation, 2005

On the complexity of factoring bivariate supersparse (Lacunary) polynomials.
Proceedings of the Symbolic and Algebraic Computation, 2005

2004
Deterministic distinct-degree factorization of polynomials over finite fields.
J. Symb. Comput., 2004

Approximate factorization of multivariate polynomials via differential equations.
Proceedings of the Symbolic and Algebraic Computation, 2004

2003
Early termination in sparse interpolation algorithms.
J. Symb. Comput., 2003

Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases.
J. Symb. Comput., 2003

On approximate irreducibility of polynomials in several variables.
Proceedings of the Symbolic and Algebraic Computation, 2003

Polynomial factorization: a success story.
Proceedings of the Symbolic and Algebraic Computation, 2003

2002
An output-sensitive variant of the baby steps/giant steps determinant algorithm.
Proceedings of the Symbolic and Algebraic Computation, 2002

Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm.
Proceedings of the Symbolic and Algebraic Computation, 2002

2000
Challenges of Symbolic Computation: My Favorite Open Problems.
J. Symb. Comput., 2000

Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm.
Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, 2000

1999
East Coast Computer Algebra Day '99 (April 24, 1999): abstracts of invited talks and presented posters.
ACM SIGSAM Bulletin, 1999

Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields.
Algorithmica, 1999

On the Genericity of the Modular Polynomial GCD Algorithm.
Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, 1999

Efficient Algorithms for Computing the Nearest Polynomial with a Real Root and Related Problems.
Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, 1999

Symbolic Computation in Java: An Appraisement.
Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, 1999

1998
Subquadratic-time factoring of polynomials over finite fields.
Math. Comput., 1998

Efficient Algorithms for Computing the Nearest Polynomial with Constrained Roots.
Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, 1998

FOXBOX: A System for Manipulating Symbolic Objects in Black Box Representation.
Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, 1998

1997
Teaching Computational Abstract Algebra.
J. Symb. Comput., 1997

Fast Polynomial Factorization Over High Algebraic Extensions of Finite Fields.
Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 1997

On Randomized Lanczos Algorithms.
Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 1997

Algebraic Algorithms.
Proceedings of the Computer Science and Engineering Handbook, 1997

1996
On Rank Properties of Toeplitz Matrices over Finite Fields.
Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, 1996

Generic Gram-Schmidt Orthogonalization by Exact Division.
Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, 1996

1995
Integer Division in Residue Number Systems.
IEEE Trans. Computers, 1995

Process Scheduling in DSC and the Large Sparse Linear Systems Challenge.
J. Symb. Comput., 1995

Effective Noether Irreducibility Forms and Applications.
J. Comput. Syst. Sci., 1995

Subquadratic-time factoring of polynomials over finite fields.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Prediction Based Task Scheduling in Distributed Computing (Abstract).
Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

On Computing Greatest Common Divisors with Polynomials Given by Black Boxes for Their Evaluations.
Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, 1995

1994
Factoring High-Degree Polynomials by the Black Box Berlekamp Algorithm.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1994

Asymptotically Fast Solution of Toeplitz-like Singular Linear Systems.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1994

1993
Direct proof of a theorem by Kalkbrener, Sweedler, and Taylor.
ACM SIGSAM Bulletin, 1993

Process Scheduling in DSC and the Large Sparse Linear Systems Challenge.
Proceedings of the Design and Implementation of Symbolic Computation Systems, 1993

Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems.
Proceedings of the Applied Algebra, 1993

1992
Polynomial Factorization 1987-1991.
Proceedings of the LATIN '92, 1992

On Computing Determinants of Matrices without Divisions.
Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, 1992

Processor-Efficient Parallel Solution of Linear Systems II: The Positive Characteristic and Singular Cases (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
On Fast Multiplication of Polynomials over Arbitrary Algebras.
Acta Inf., 1991

Effective Noether Irreducibility Forms and Applications (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Processor Efficient Parallel Solution of Linear Systems over an Abstract Field.
SPAA, 1991

DSC: A System for Distributed Symbolic Computation.
Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, 1991

On Wiedemann's Method of Solving Sparse Linear Systems.
Proceedings of the Applied Algebra, 1991

1990
Computing with Polynomials Given By Black Boxes for Their Evaluations: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators.
J. Symb. Comput., 1990

Special Issue Computational Algebraic Complexity Editorial.
J. Symb. Comput., 1990

Computing the Irreducible Real Factors and Components of an Algebraic Curve.
Appl. Algebra Eng. Commun. Comput., 1990

Modular Rational Sparse Multivariate Polynomial Interpolation.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1990

1989
Factorization of Polynomials Given by Straight-Line Programs.
Advances in Computing Research, 1989

An Improved Las Vegas Primality Test.
Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation, 1989

Solving Systems of Nonlinear Polynomial Equations Faster.
Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation, 1989

Computing the Irreducible Real Factors and Components of an Algebraic Curve.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

Computers and mathematics.
Springer, ISBN: 0387970193, 1989

1988
Dagwood: a system for manipulating polynomials given by straight-line programs.
ACM Trans. Math. Softw., 1988

Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits.
SIAM J. Comput., 1988

Greatest common divisors of polynomials given by straight-line programs.
J. ACM, 1988

Analysis of the binary complexity of asymptotically fast algorithms for linear system solving.
ACM SIGSAM Bulletin, 1988

Improved Sparse Multivariate Polynomial Interpolation Algorithms.
Proceedings of the Symbolic and Algebraic Computation, 1988

Computing with Polynomials Given By Black Boxes for Their Evaluation: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
Deterministic Irreducibility Testing of Polynomials over Large Finite Fields.
J. Symb. Comput., 1987

Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Mr. Smith goes to Las Vegas: Randomized parallel computation of the Smith Normal Form of polynomial matrices.
Proceedings of the EUROCAL '87, 1987

1986
Uniform Closure Properties of P-Computable Functions
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Fast parallel algorithms for similarity of matrices.
Proceedings of the SYMSAC 1986, 1986

A system for manipulating polynomials given by straight-line programs.
Proceedings of the SYMSAC 1986, 1986

Efficient Parallel Evaluation of Straight-line Code and Arithmetric Circuits.
Proceedings of the VLSI Algorithms and Architectures, 1986

1985
Effective Hilbert Irreducibility
Information and Control, September, 1985

Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization.
SIAM J. Comput., 1985

Fast Parallel Absolute Irreducibility Testing.
J. Symb. Comput., 1985

Factoring Sparse Multivariate Polynomials.
J. Comput. Syst. Sci., 1985

Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Computing with Polynomials Given by Straight-Line Programs II: Sparse Factorization
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Arithmetic in Quadratic Fields with Unique Factorization.
Proceedings of the EUROCAL '85, 1985

Sparse Hensel Lifting.
Proceedings of the EUROCAL '85, 1985

1984
Explicit Construction of the Hilbert Class Fields of Imaginary Quadratic Fields with Class Numbers 7 and 11.
Proceedings of the EUROSAM 84, 1984

A Note on the Risch Differential Equation.
Proceedings of the EUROSAM 84, 1984

Effective Hilbert Irreducibility.
Proceedings of the EUROSAM 84, 1984

1983
A Generalized Class of Polynomials that are Hard to Factor.
SIAM J. Comput., 1983

Polynomial-Time Factorization of Multivariate Polynomials over Finite Fields.
Proceedings of the Automata, 1983

On the complexity of finding short vectors in integer lattices.
Proceedings of the Computer Algebra, 1983

1982
Polynomial reduction from multivariate to bivariate integral polynomial factorization.
ACM SIGSAM Bulletin, 1982

A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981
A generalized class of polynomials that are hard to factor.
Proceedings of the SYMSAC 1981, 1981


  Loading...