报告题目:Linear time interactive certificates for the MinPoly & Determinant of a sparse matrix
报 告 人：Erich Kaltofen,  NCSU and Duke Univ.
主 持 人：杨争峰 副教授
报告时间：2018年6月7日 周四 14:00-15:30
报告地点：中北校区数学馆东202

报告人简介：

Erich Kaltofen received both his Ph.D. degree in Computer Science in 1982 from Rensselaer Polytechnic Institute. He was an Assistant Professor of Computer Science at the University of Toronto and an Assistant, Associate, and full Professor at Rensselaer Polytechnic Institute. Since 1996 he is a Professor of Mathematics at North Carolina State University.  Since 2017 he is also affiliated with Duke University.  He has held visiting positions at MSRI Berkeley, ENS Lyon, MIT, UPMC Paris, U. Grenoble, and U. Waterloo. Kaltofen's current interests in the symbolic computation discipline are hybrid symbolic/numeric algorithms, efficient algorithms for sparse interpolation and error correction and interactive proofs.  Kaltofen has designed several algorithms for polynomial factorization including one for polynomials in straight-line representation.Kaltofen was the Chair of ACM's Special Interest Group on Symbolic & Algebraic Manipulation 1993 - 95. From 1985 - 87 he held an IBM Faculty Development Award. In 2009 Kaltofen was selected an ACM Fellow. He has edited 4 books, including the Computer Algebra Handbook in 2002, published over 170 research articles.

报告摘要：

Computational problem  certificates are additional data structures for each output,which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output.  In this talk, we give an algorithm that computes a certificate for the minimal polynomial of sparse or structured nxn matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear number of extra field operations.  We also propose a novel preconditioner that ensures irreducibility of the characteristic polynomial of the generically preconditioned matrix.  This preconditioner takes linear time to be applied and uses only two random entries.  We then combine these two techniques to give algorithms that compute certificates for the determinant, and thus for the characteristic polynomial,whose Monte Carlo verification complexity is therefore also linear.